Brandon threw a party where lots of fireworks were detonated. In particular, Brandon detonated $N$ unique fireworks. He now has a lot of fireworks to clean up.

Brandon has $N$ trash cans, each of which can store up to $K$ firework wrappers. Brandon will execute a move that he has dubbed the Trash Push, where he takes all of the firework wrappers he has and pushes them into the nearest trash can. Brandon is so skilled at executing the Trash Push that if there are too many firework wrappers in the nearest trash can, exactly the overflowing wrappers will fall into another trash can. This process of exactly the overflowing trash falling into another trash can will continue until no trash can is overflowing.

After Brandon executes the Trash Push on the $N$ firework wrappers he has, how many trash cans will have at least one firework wrapper in them?

Constraints

$1\le T\le {10}^4$

$1\le N,K\le {10}^9$

Input Specification

The first line contains a single positive integer $T$, the number of test cases.

$T$ lines follow. Each of these lines contains two space-separated positive integers, $N$ and $K$.

Output Specification

Output $T$ lines. On the $i$th line, output the number of trash cans that have at least one firework wrapper in them for the $i$th test case.

Sample Input

3
1 1
3 14
3939 39

Sample Output

1
1
101