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
Jaswanth:
20150821 19:57:41
nice problem try to find the pattern 

Ankit:
20150413 12:22:44
my 50th : ) ,nice one


californiagurl:
20140719 19:10:21
getting TLE with vector. did anyone get AC using vector? 

abhay srinivas:
20140531 21:01:04
Last edit: 20140531 21:51:08 

fitcat:
20140318 08:12:51
Doesn't a set ensure all members are distinct? I think it should be rephrased as "for any number x belonging to S, k*x does not belong to S." Anyway, nice one.


californiagurl:
20140317 05:38:59
Last edit: 20140317 07:18:16 

anurag garg:
20140307 09:16:15
@nitish rao can you check my solution id:11198262


Flago:
20140307 09:16:15
Case K=1 got me a TLE :D 

Kanish_The_Vista:
20140307 09:16:15
Last edit: 20140306 18:06:07 

Kanish_The_Vista:
20140307 09:16:15
Last edit: 20140306 18:06:18 
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 