Problem F: Colossal Fibonacci Numbers!

The i'th Fibonacci number f (i) is recursively defined in the following way:

• f (0) = 0 and f (1) = 1
• f (i+2) = f (i+1) + f (i)  for every i ≥ 0

Your task is to compute some values of this sequence.

Input begins with an integer t ≤ 10,000, the number of test cases. Each test case consists of three integers a,b,n where 0 ≤ a,b < 2⁶⁴ (a and b will not both be zero) and 1 ≤ n ≤ 1000.

For each test case, output a single line containing the remainder of f (a^b) upon division by n.

Sample input

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

1
21
250