KATHTHI2 - Coin Fight

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

Added by:cegprakash
Date:2016-10-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: MAWK BC BF NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.