×

计蒜客

  1. 题库
  2. super_log
  3. 问答
  • 15.97%
  • 131072K

In Complexity theory, some functions are nearly $O(1)$, but it is greater then $O(1)$. For example, the complexity of a typical disjoint set is $O(nα(n))$. Here $α(n)$ is Inverse Ackermann Function, which growth speed is very slow. So in practical application, we often assume $α(n) \le 4$.

However $O(α(n))$ is greater than $O(1)$, that means if $n$ is large enough, $α(n)$ can greater than any constant value.

Now your task is let another slowly function $log*$ $x$ reach a constant value $b$. Here $log*$ is iterated logarithm function, it means “the number of times the logarithm function iteratively applied on $x$ before the result is less than logarithm base $a$”.

Formally, consider a iterated logarithm function $log_{a}^* $

Find the minimum positive integer argument $x$, let $log_{a}^* (x) \ge b$. The answer may be very large, so just print the result $x$ after mod $m$.

Input

The first line of the input is a single integer $T(T\le 300)$ indicating the number of test cases.

Each of the following lines contains $3$ integers $a$ , $b$ and $m$.

$1 \le a \le 1000000$

$0 \le b \le 1000000$

$1 \le m \le 1000000$

Note that if a==1, we consider the minimum number x is 1.

Output

For each test case, output $x$ mod $m$ in a single line.

Hint

In the $4-th$ query, $a=3$ and $b=2$. Then $log_{3}^* (27) = 1+ log_{3}^* (3) = 2 + log_{3}^* (1)=3+(-1)=2 \ge b$, so the output is $27$ mod $16 = 11$.

样例输入

5
2 0 3
3 1 2
3 1 100
3 2 16
5 3 233

样例输出

1
1
3
11
223

想挑战这道题吗

  • main.c