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

Explanation:

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


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

hide comments
2015-08-21 19:57:41 Jaswanth
nice problem try to find the pattern
2015-04-13 12:22:44 Ankit
my 50th : ) ,nice one


Last edit: 2015-04-13 12:24:16
2014-07-19 19:10:21 californiagurl
getting TLE with vector. did anyone get AC using vector?
2014-03-18 08:12:51 fitcat
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.



Last edit: 2014-03-19 06:03:35
2014-03-07 09:16:15 anurag garg
@nitish rao can you check my solution id:11198262
what is the expected complexity I am getting TLE
AC....:)
after 30 so many TLE SIGSEGV and WA

Last edit: 2014-03-17 16:50:23
2014-03-07 09:16:15 Flago
Case K=1 got me a TLE :D
2014-03-07 09:16:15 Bhavik
finaaly AC!! my stupidity costed me so many tle's wa..

Last edit: 2014-03-06 18:35:10
2014-03-07 09:16:15 RIVU DAS
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
2014-03-07 09:16:15 Zenith
nice one

Last edit: 2014-03-06 18:07:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.