Little boy Sai is fascinated with Natural Numbers. He especially likes Special Sets of order k. A set of numbers S, is called Special Set of order k if, for any two numbers x and y (not necessarily distinct) belonging to S, x should not be equal to k×y.

Now, Sai wants to find the size of maximum possible Special Set formed out of the numbers 1, 2, 3 ... n. Hope you can help him.

Input

First line contains t (1 ≤ t ≤ 10⁵), the number of test cases. Next t lines contain two space separated integers n and k.

1 ≤ n, k ≤ 10⁸.

Output

For each test case, output on a single line the size of maximal Special Set.

Example

Input:
1
6 2
Output:
4

Explanation:

For the above case, the maximal Special Set is: 1, 3, 4, 5