2011年12月17日 星期六

11246 - K-Multiple Free set

我們定義一個「不存在相對k倍的整數集合」(k-multiple free set)為一整數集合中任兩個整數中的一個不會是另一個的k倍,例如當k=2,{1, 3, 4}是合法的,但{2, 4, 5}並不是,因為4為2的2倍。

給定 n 與 k 之值,請你從1~n的整數集合中,找出最大的"k-multiple free set"共有幾個整數。


Input
輸入資料的第一列有一個整數T(1 <= T <= 1000)表示測試資料的組數,接下來有T組測試資料,每組一列有兩個整數 n (1 <= n <= 1000000000),k (2 <= k <= 100)。

Output

請每組測試資料輸出一個整數,表示在1 ~ n之中屬於k-multiple free set的子集最多共有幾個整數。

Sample Input                            Output for Sample Input

3
10 2
100 2
1000 2

6
67
666


沒有留言:

張貼留言