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.

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