Description

White is playing Reversi with a forest spirit race, but the rules of Reversi have been changed.

There are $n$ Reversi pieces. The $i$-th piece is labeled $i$. All pieces are initially black. During the game, only White operates. White wants to turn as many pieces as possible to white.

White requires that piece $k$ and piece $k \times p$ cannot both be turned white at the same time.

White played $T$ games in total. In each game, White wants to know the maximum number of pieces that can be turned white. Each game is independent.

To avoid confusion, the bold White is a person’s name.

Input Format

The first line contains a positive integer $T$, denoting the number of test cases.

The next $T$ lines each contain two integers $n, p$, as described.

Output Format

Output $T$ lines. Each line contains one positive integer, denoting the maximum number of pieces that White can turn white.

1
3 2

2

1
100 5

84

Hint

Sample 1 Explanation

You can choose pieces $2, 3$ to change color.

Constraints

This problem uses bundled tests.

• Subtask 1 (5 pts): $T \le 5$, $n \le 2$;
• Subtask 2 (5 pts): $T \le 5$, $n \le 10$;
• Subtask 3 (20 pts): $T \le 5$, $n \le 10^6$;
• Subtask 4 (70 pts): no special constraints.

For $100\%$ of the testdata, $1 \le T \le 10^6$, $0 \le n \le 10^{18}$, $1 \le p \le 10^{9}$.

// Fast input template
// During-contest reminder: fast input is not very necessary
inline long long read(){
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}

Translated by ChatGPT 5