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

---

原文出處