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 .
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 .
Print exactly lines with the corresponding on each line.
Sample Input 0
3 3 1000000000000000000
Sample Output 0