Given a positive integer X, an operation on X is defined as follows:
Split X into powers of 10 such that the number of integers into which X is split, is minimum.
Let A define the array containing all integers of the split.
Sort the array A in non-increasing order.
Concatenate the elements of A and assign the value to X.

For example, an operation on X = 22 looks like:
Splitting 22 into minimum number of integers such that each is integer is a power of 10.
Here, 22 = 1 + 1 + 10 + 10. Thus, A = [1, 1, 10, 10].
Sorting the array A in non-increasing order. Thus, A = [10, 10, 1, 1].
Concatenating the elements of A gives 101011. Thus, the new value of X = 101011.

Kulyash has given you two integers N and K.

You need to perform the above-mentioned operation K times on the integer N. Find the number of digits in the final integer. Since the answer can be huge, output it modulo 998244353.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first and only line of each test case contains two space-separated integers N and K — the initial number and the number of operations to be performed.

------ Output Format ------

For each test case, output on a new line, the number of digits in the final number after K operations are performed on N, modulo 998244353.

------ Constraints ------

$1 ≤ T ≤ 10^{2}$
$1 ≤ N ≤ 10^{10^{4}}$
$0 ≤ K ≤ 10^{9}$

------ subtasks ------

Subtask 1 (40 points): $1 ≤ N ≤ 10^{3}$
Subtask 2 (60 points): Original constraints

----- Sample Input 1 ------
2
101 3
32 1

----- Sample Output 1 ------
6
8

----- explanation 1 ------
Test case $1$: Let us perform $3$ operations on $101:$
- Operation $1$ — $101 = 100 + 1$, thus $N = 1001$
- Operation $2$ — $1001 = 1000 + 1$, thus $N = 10001$
- Operation $3$ — $10001 = 10000 + 1$, thus $N = 100001$. The final value of $N$ is $100001$ which has $6$ digits.

Test case $2$: $32 = 10 + 10 + 10 + 1 + 1$, thus $N = 10101011$, which has $8$ digits.

见题面

见题面