You are given a starting salary S, a duration of N years, and a target salary G.

The salary grows by an integer growth factor X every year.

After N years, Salary = S*(X)^N

Find the minimum integer value of X such that

S*(X)^N≥G

The first line contains an integer T — the number of test cases.

Each of the next T lines contains three integers:

S N G

Output

For each test case, print the minimum integer growth factor X.