Background

Marisa is an ordinary and plain magician. After resolving all kinds of incidents, she finally saved enough money to buy a $\verb!Carno!$ calculator at Kourindou, used to compute the ratios of various ingredients in the Witch's Soup.

Marisa had long heard that Reimu bought a $\verb!Casio!$ calculator through the Kappa Heavy Industries network here to calculate the shrine's donation money, but she ended up buying a fake one that could display at most only the integer part (floor). Marisa's calculator can be accurate to a certain number of digits after the decimal point (also by flooring). Even more advanced, it supports other bases as well, making it much more powerful than Reimu's. Therefore, as Reimu's sincere friend, Marisa wants to express her sincere regret to Reimu.

Just as Marisa was about to leave, she noticed that although the $\verb!Carno!$ calculator would not cause particularly large errors, it could still have some issues when doing division. Consider setting the calculator's base to base $10$, and the screen can display at most $5$ digits (the decimal point does not count as a displayed digit). For example, if Marisa wants to compute $1\div 3$, then what is actually shown on the screen is:

$$0.3333$$

In theory, the result of $1\div(1\div 3)$ should equal $3$. But surprisingly, when Marisa inputs $1\div 0.3333$, the result she gets is:

$$3.0003$$

Of course, this is only one example. When Marisa computes $1\div(1\div 4)$, the screen shows the correct number.

To prevent her calculator from messing up when she expresses her regret, Marisa wants to find how many numbers will produce the correct result, so she asks you for help.

Problem Description

Marisa's calculator can perform computations in base $b$, and the screen can display $k$ digits (not including the decimal point). After a computation, if some digits exceed the screen capacity, they are directly discarded (for example, when $b=10$, $1\div 7=0.142857\cdots$; if the screen size is $4$, then the final display is $0.142$).

Marisa uses the calculator to compute $1\div n=n'$, and then computes $1\div n'=n''$ ($n'$ and $n''$ are both the results shown on the screen). Marisa wants to know how many positive integers $n$ satisfy $n=n''$. You only need to output this count modulo $998,244,353$.

Input Format

• The first line contains a positive integer $T$, the number of test cases.
• The next $T$ lines each contain two positive integers $b,k$, representing the calculator's base and the number of digits the screen can display.

Output Format

• Output $T$ lines in total.
• Each line outputs one integer. The integer on the $i$-th line is the number of valid $n$ in the $i$-th test case, modulo $998,244,353$.

3
4 2
5 3
12 99

3
3
19503

Hint

Sample Explanation

• For the first query, the numbers that satisfy the condition (converted to decimal) are $1,2,4$.
• For the second query, the numbers that satisfy the condition (converted to decimal) are $1,5,25$.

Constraints and Conventions

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{subtask}&\textbf{Score} & \bm{b\le} & \bm {k\le } & \textbf{Special Properties} & \textbf{subtask Dependencies} \cr\hline 1 & 20 & 10 & 7 & - &-\cr\hline 2 & 20 & 10^5 & 2 & k=2&-\cr\hline 3 & 10 & 10^5 & 3 & k=3&- \cr\hline 4 & 50& 10^5 & 500 & -&1,2,3\cr\hline \end{array}$$

For $100\%$ of the testdata, it holds that $1\le T\le 10$, $2\le b\le 10^5$, $1\le k\le 500$.

Translated by ChatGPT 5