Description

We call a number EXcellent if it divided by 11 euqals 0 or it contains the number k, see sample for details.

Now we want to know how many EXcellent numbers are between [0, 10ⁿ] ?

Since this number can be very large, print the remainder when it’s divided by lovely 998244353.

Input

The first line contains an integer T(T ≤ 10) — the number of test cases you need to solve.

The only line of each test case contains 2 integer n, k(1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 2 × 10⁵) without leading zeros. test case, print the result mod lovely 998244353.

Output

For each test case, print the result mod lovely 998244353.

3
1 1
2 12
666 233

3
11
828654121

Hint

In the first example, there are 0,1,10 In the second example, there are 0,11,12,22,33,44,55,66,77,88,99