SPEC_SET - Special Set


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<=105), the number of test cases. Next t lines contain two space separated integers n and k.

1<=n,k<=108

Output

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

Example

Input:
1
6 2

Output:
4
Explaination:
For the above case, the maximal Special set is: 1,3,4,5


hide comments
Bhavik: 2014-03-07 09:16:15

finaaly AC!! my stupidity costed me so many tle's wa..

Last edit: 2014-03-06 18:35:10
RIVU DAS: 2014-03-07 09:16:15

Can u check what is wrong with my solution??

--nitish--> Check the answer for n=16,k=2. You are getting 1 less than the correct answer

Last edit: 2014-03-05 17:39:42
Zenith: 2014-03-07 09:16:15

nice one

Last edit: 2014-03-06 18:07:37
Jacob Plachta: 2014-03-07 09:16:15

The constraint that x should not be equal to k*y also applies to x=y.

--nitish--> Thanks for pointing out. Updated the question now.

Last edit: 2014-03-05 07:16:31

Added by:nitish rao
Date:2014-03-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:My own Problem