The i'th Fibonacci number f (i) is recursively defined in the following way:
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 < 264 (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 (ab) upon division by n.
3 1 1 2 2 3 1000 18446744073709551615 18446744073709551615 1000
1 21 250