P10322 Purity

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*.

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$).

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 $T$ lines, each line containing the answer for one test case.

[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: $$\left(\sum_{i=1}^{15}i\right)-6-12+6^3+12^2=462$$ 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