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