时间限制： 1.0 秒

空间限制： 256 MB

题目描述

阿克曼（Ackermann）函数 $A(m,n)$ 中，$m,n$ 定义域是非负整数，函数值定义为：

$$A(m,n) = \begin{cases} n+1, & m = 0 \\ A(m-1,1), & m>0,n=0 \\ A(m-1,A(m,n-1)), & m,n>0 \end{cases} $$

给定非负整数 $m,n$，请你求出对应的 $A(m,n)$。

输入格式

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

输入一行两个非负整数 $m,n$。

输出格式

输出到标准输出。

对于每组测试数据：

输出一行一个整数，为对应的函数值。

2
0 0
2 3

1
9

子任务

对于所有数据，保证 $m\le 3,n\le 10$。

提示

邓俊辉《习题解析》[1-27]

本题可以用于练习函数和递归的基础操作，虽然加入记忆化搜搜也可以，但是需要注意记忆化搜索当中，$n$ 的上限。此外，在 $m\le 3$ 的情况下，阿克曼函数针对不同的 $m$ 都有对应的通项公式，可以进行搜索查阅~

与 HailStone 序列不同，Ackermann 函数是一个有穷的函数，尽管在 $m\ge 4$ 的情况下，答案会巨大无比（例：$A(4,2)=2^{65536}-3,A(4,4)\approx 2^{2^{10^{19729}}}$）。

此外，其对应的函数为反阿克曼函数 $\alpha(n)$。由于阿克曼函数的增长效率非常快，因此对于一般的 $n$，都有 $\alpha(n)\le 4$，基本上可以被视为常数。反阿克曼函数在后续图论一章当中的并查集会用到，在并查集同时做了路径压缩+按规模/秩的启发式合并的优化时，单次操作的最坏复杂度上界即为 $O(\alpha(n))$。