Background

Simple, accurate, and everlasting beauty — Purity.

“Light of Purity” Ram, as the Elf King, can perfectly use the power of The Ames Grass Paper Book.

Problem Description

Ram uses “Storm Arrow Rain” and shoots $n$ arrows at once. The original attack power of the $i$-th arrow is $i$. However, these arrows will receive some enhancements.

For a constant $d$, define the energy level of an arrow with original attack power $i$ as $v(i)$:

• If there does not exist a positive integer $k$ such that $i^k$ is a multiple of $d$, then $v(i)=0$;
• Otherwise, $v(i)$ is the smallest positive integer $k$ such that $i^k$ is a multiple of $d$.

Then the enhanced attack power of this arrow is $i^{v(i)+1}$.

Ram wants to know the sum of the attack powers of all arrows after enhancement. Since the answer may be very large, you only need to output the result modulo $998244353$ (that is, the remainder when dividing the answer by $998244353$).

Input Format

The first line contains a positive integer $T$, the number of test cases.
The next $T$ lines each contain two positive integers $n,d$, with meanings as described above.

Output Format

Output $T$ lines, each line containing the answer for one test case.

5
15 12
400 2520
5000000 68256
10000000 65536
10000000000 3628800

462
946645637
231125775
290821843
602104955

Hint

[Sample Explanation]
For the first test case, $d=12$. Here $v(6)=2$ because $12$ divides $6^2$ but does not divide $6^1$. Similarly, we have $v(12)=1$.
It can be seen that all other numbers up to $n=15$ have energy level $0$, so the answer is:

For the second test case, it can be proved that within $n$ only $v(210)=3$ is non-zero. From this, the answer is $1944889990$, and after taking modulo $998244353$ it becomes $946645637$.

[Constraints]
This problem uses bundled tests.

Subtask 1 (15 pts): $1 \le n,d \le 10^4$;
Subtask 2 (15 pts): $d$ is prime;
Subtask 3 (20 pts): $d$ is a positive integer power of a prime;
Subtask 4 (20 pts): there does not exist an integer $x>1$ such that $x^4$ divides $d$;
Subtask 5 (30 pts): no special restrictions.

For all data, $1\le T \le 1000$, $1\le n < 2^{63}$, $1\le d \le 10^8$.

[Hint]
The time limit for this problem is relatively generous. Even if your code is not optimized in some details, it can still pass normally.

Translated by ChatGPT 5