U472940 阿克曼函数

- 阿克曼函数（$\text{Ackermann}$）是非原始递归函数的经典例子。 - 它以两个自然数 $x,y$ 作为输入值，返回一个自然数 $\operatorname{Ackermann}(x,y)$，它的输出值增长速度非常快，下面是一个简单的例子： - 设 $a(\operatorname{Ackermann}(x,x))=O(x)$，那么 $a(x)=O(a(\log x))$。 - 虽然当 $x,y$ 稍大之后，阿克曼函数的确切值，甚至它的位数，都不存在求出来的可能性，但你只需要求出它模一个小整数 $p$ 的结果，而这是容易做到的。

- 下面是阿克曼函数的定义式： $$\operatorname{Ackermann}(x,y)=\begin{cases}y+1&x=0\\\operatorname{Ackermann}(x-1,1)&x>0,y=0\\\operatorname{Ackermann}(x-1,\operatorname{Ackermann}(x,y-1))&\text{otherwise.}\end{cases}$$ - 给定 $T$ 组 $x,y,p$ 三元组，你需要求出 $\operatorname{Ackermann}(x,y)\bmod p$ 的结果。

- 第一行，一个自然数 $T$。 - 接下 $T$ 行，三个自然数 $x,y,p$。

- $T$ 行每行一个整数，表示对应询问的 $\operatorname{Ackermann}(x,y)\bmod p$。

- 对于所有数据 $0\le T\le 300$，$0\le x,y\le 10^9$，$1\le p\le 10^9$。 - 不保证 $p$ 是质数。