Sathish and Kathiresan are known for Coin Fight. Kathiresan kept on tossing a biased coin repeatedly. Then he decided to solve the following problem.

Find the number of tosses for which the probability of getting exactly K heads is maximum. In case of a tie, return the minimum number of tosses.

In other words, find the minimum n such that probability (exactly K heads with n tosses) >= probability (exactly K heads with m tosses) for any m!=n.

Input:

The first line consists of an integer t, the number of test cases. For each test case you are given an integer K, the number of heads required and a float p, the probability to get a head when the coin is tossed.

Output:

For each test case find the number of tosses required as defined.

Input Constraints:

1 <= t <= 100

1 <= K <= 100

0.00 < p <= 1.00

p will always contain a maximum of 2 decimal places

Sample

Input:
3
5 1.00
1 0.50
2 0.30

Output:
5
1
6