JUMPBALL - THE JUMPING BALL

A ball is dropped from a height 'h' and it bounces at a bouncing constant 'b' i.e. the ball bounces back to a height that is 1/b times the height from which it was originally dropped. So given h and b we need to find the number of times the ball bounces before it comes to halt. Any height less than 1m can be considered as the halt.

Input

First line contains the number of test cases t. 1 <= t <= 100000.

The next 't' lines each contain 2 space separated integers 'h' and 'b'.

1 <= h <= 10^9

2 <= b <= 30

Output

For each test case output a single line containing the answer.

Example

Input:
2
8 2
2 9

Output:
3
0

Added by:cegprakash
Date:2013-01-20
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

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