Project Euler #188: The hyperexponentiation of a number

_{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