A fantastic discovery is about to happen in the biology field, and you are part of the team making the research. The research is about measuring the cells growth in an environment oxygen less and in presence of a toxic substance. The team came to a curious hypothesis, the analyzed data tells them that: the growth, the number of days and the toxicity; are related by this formula:

P = N*N^cN

where P is the growth measured in thousands of cells.

N is the elapsed number of days.

and c is the constant that relates to the toxicity level of the experiment.

Your biology partners need to takeout some tissues from the cells when these cells reach a specific growth. They require you to write a program that tells them the exact time when this will happen, given a toxicity level and the growth required.

Input

The first line is T (1 ≤ T ≤ 40,000), the number of test cases, then T test cases follow.

Each test case is a line with 2 integers (P c) separated by a space.

P (1 ≤ P ≤ 10¹⁵)

c (1 ≤ c ≤ 5)

Output

For each test case you have to output the expected time in decimal format.

Example

Input:
3
1 1
3 4
100 1

Output:
1.000000
1.207384
3.086308

Note 1: your output must contain at least 6 decimal places.

Note 2: numerical problem. Output generated by submitted program should be exactly the same as test case with accuracy of 0.000001.