Little boy maze invented a brand new data type that can store data from 1 to M inclusive. The speciality of the invented data type is if you want to store a data out of the range it can round the data and map with invented data type.

for example if the range is 1 to 7 and you want to store 9 then the system round 9 and map with 2.

Now you're given a number in the format  A^B and the upper limit M of range. Can you round the number to map with new data type?

Input

Input starts with T <= 100000.

in the next T lines there will be three integers(1 <= A, B <= 1000000000000000000, 1 < M < 1000000000).

Output

For each case print the desire output.

Example

Input:
2
2 3 5
4 2 15
Output:
3
1