Migrated from Lutece 102 Qmm and Tmm

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

It has been said that hard-working girl is the most beautiful. In order to become the most beautiful girl in UESTC, Qmm is trying solving all the problems on all online judges including POJ and CDOJ recently. What a tremendous task! As everyone knows, there are thousands of problems online and several ones are beyond her ability. However, stubborn Qmm thinks she can achieve her goal in only one year. From the start of every day (Yes, the start! i.e. $0$ o’clock), she wakes up to find problems and write codes without a break. As the best friend of Qmm, Tmm always kindly persuade Qmm to relax for the rest of the day whenever Qmm is too tired to go on. Let's use a value $P$ to represent Qmm's strength. Solving problems will cost some time and strength of QMM. It takes QMM $D$ hours to solve the $D_{th}$ problem. And apart from that, the strength of Qmm will be decreased by $D$. The $D$ is counted from the latest sleep while assuming Qmm has a good sleep before the beginning. The initial strength of Qmm may be very large.

Every time the strength of Qmm is smaller than the cost of the next problem, Tmm will come and drag Qmm to sleep for the rest hours of the day.Note that the time for sleep may be zero. After Qmm having an hour of sleep, her strength will increase by one.

Given the strength $P_0$ of Qmm at the beginning, you are required to calculate the number of problems she solved after $N$ days.

Input

The first line of the input is $T$ (no more than $10000$), which stands for the number of test cases you need to solve. Each line of the following $T$ lines will give $2$ numbers, the initial strength $P_0$ and $N$. ($0 < P_0, N\leq 100000000$)

Output

Please output the number of problems Qmm solved for each test case.

Samples

4
10 1
10 2
10 3
30 4

4
8
13
15

Resources

The 8th UESTC Programming Contest Preliminary