This problem is a programming version of Problem 188 from projecteuler.net
The or of a number by a positive integer , denoted by or , is recursively defined by:
,
.
Thus we have e.g. , hence and is roughly .
Find .
Input Format
The first line of each test file contains a single integer which is the number of queries you have to process. lines follow, each containing three integers separated by single spaces: , and .
Constraints
Output Format
Print exactly lines with the corresponding on each line.
Sample Input 0
1
3 3 1000000000000000000
Sample Output 0
7625597484987