Background

During-contest reminder: If you always get 30 pts and you used the fast input provided in the problem, please copy the modified fast input again.

During-contest reminder: If your solution is correct, fast input may not help optimize.

This is probably a struggle that cuts existence and even memories into thirty-two pieces, played as Reversi.

The numbers of remaining pieces on both sides are very small—meaning they are very important.

......

—Why would Brother let himself be left alone? She was originally confused about this.

However, after learning the answer, it can only be said that it was a natural thing to do.

First, the first reason is extremely simple.

Deliberately entrusting memories to the other side, and temporarily staying in a losing position, was for the purpose of—

「...That kind of thing... White... can't do it...」

Imagining it for a moment, White showed a sad smile and reached this conclusion.

If what Brother did were carried out by White... White does not think her mind could remain normal.

Just because Brother disappeared from her side, she even once doubted Brother’s existence.

—If she were forgotten, that would be fine.

—If she forgot Brother—White was sure her mind would not be able to remain normal.

......

(...Here... Brother is... here...)

Even in a space with nothing at all, White was sure she could feel where Brother was.

White’s eyes suddenly felt hot, but she forced herself to hold back and kept thinking.

(...And then this is... the second... and also... the biggest... reason.)

White held the piece marked 【参】 with its white side facing up, pinching it with her fingers.

There was no need to hesitate about the question of whether Brother was “white or black”.

Because since he entrusted the final game to “White”—then of course he was playing as white.

This game that cannot be seen now, and cannot even be perceived.

There is neither memory of the start, nor is it known how the board evolved.

But the moves Brother could have played, deliberately losing, and in order to let White win...

And the moves the opponent, after seeing them, completely fell into Brother’s trap and was guided to play...

Then, all the possible position choices Brother might make in order to turn the game around.

Infer and analyze all of these—win by turning defeat into victory in only three moves.

......

And then—the memories that were originally lost for one and a half days—flowed back upstream—

Problem 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