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