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<=10^{5}), the number of test cases. Next t lines contain two space separated integers n and k.
1<=n,k<=10^{8}
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:
20140307 09:16:15
finaaly AC!! my stupidity costed me so many tle's wa.. Last edit: 20140306 18:35:10 

RIVU DAS:
20140307 09:16:15
Can u check what is wrong with my solution??


Zenith:
20140307 09:16:15
nice one Last edit: 20140306 18:07:37 

Jacob Plachta:
20140307 09:16:15
The constraint that x should not be equal to k*y also applies to x=y.

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