Maximizing White Chess Pieces

In this problem, White is playing a modified version of the game using black and white chess pieces. Initially, there are (n) chess pieces numbered from (1) to (n), and all of them are black. White wishes to turn as many pieces as possible white; however, there is a restriction: for every integer (k) such that (k\times p \le n), the (k^{th}) piece and the ((k\times p)^{th}) piece cannot both be white simultaneously.

You are given (T) independent games. In each game, you are provided with two integers (n) and (p) (with (p\ge2)). Your task is to determine the maximum number of pieces that can be turned white while satisfying the above condition.

A useful insight is to observe that the restriction only applies between a number and its multiple by (p). Therefore, the pieces can be partitioned into disjoint chains: for every number (i) that is not divisible by (p), consider the chain (i, i\times p, i\times p^2, \dots) (as long as the terms do not exceed (n)). In each chain, for every valid link the two consecutive pieces cannot both be white. The problem then reduces to finding the maximum independent set in a path (chain) where the optimal is (\lceil\frac{L}{2}\rceil) for a path of length (L). The final answer is the sum of these contributions over all chains.

inputFormat

The first line contains an integer (T) denoting the number of test cases. Each of the following (T) lines contains two space‐separated integers (n) and (p) (with (2\le p\le n\le 10^{12})).

outputFormat

For each test case, output a single line containing the maximum number of pieces that can be turned white while satisfying the condition.

sample

3
10 2
15 3
20 2

6
11
14