{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn 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$.\u003c/p\u003e\n\u003cp\u003eHowever $O(α(n))$ is greater than $O(1)$, that means if $n$ is large enough, $α(n)$ can greater than any constant value.\u003c/p\u003e\n\u003cp\u003eNow 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$”.\u003c/p\u003e\n\u003cp\u003eFormally, consider a iterated logarithm function $log_{a}^* $\u003cimg src\u003d\"CDN_BASE_URL/d06af13cf18824446b028d4aff79cb2f?v\u003d1666082580\" alt\u003d\"\"\u003e\u003c/p\u003e\n\u003cp\u003eFind 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$.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line of the input is a single integer $T(T\\le 300)$ indicating the number of test cases.\u003c/p\u003e\n\u003cp\u003eEach of the following lines contains $3$ integers $a$ , $b$ and $m$.\u003c/p\u003e\n\u003cp\u003e$1 \\le a \\le 1000000$\u003c/p\u003e\n\u003cp\u003e$0 \\le b \\le 1000000$\u003c/p\u003e\n\u003cp\u003e$1 \\le m \\le 1000000$\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eNote that if a\u003d\u003d1, we consider the minimum number x is 1.\u003c/b\u003e\u003cbr\u003e\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case, output $x$ mod $m$ in a single line.\u003c/p\u003e\n\u003ch3\u003eHint\u003c/h3\u003e\n\u003cp\u003eIn the $4-th$ query, $a\u003d3$ and $b\u003d2$. Then $log_{3}^* (27) \u003d 1+ log_{3}^* (3) \u003d 2 + log_{3}^* (1)\u003d3+(-1)\u003d2 \\ge b$, so the output is $27$ mod $16 \u003d 11$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n2 0 3\n3 1 2\n3 1 100\n3 2 16\n5 3 233\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n3\n11\n223\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}