Given a positive integer $n$, in each turn:

1. Uniformly choose a digit $d$ from $n$ (in decimal representation).
2. Update $n$ by setting $n\leftarrow n\cdot(d+1)$.

Calculate the expected number of turns it takes for $n$ to exceed $N$, modulo $998244353$.

Input

There are multiple test cases in a single test file.

The first line of the input contains a single integer $T$ ($1\le T\le 200$), indicating the number of the test cases.

For each test case, the first line of the input contains two integers $n$ and $N$ ($1\le n\le N\le 10^{18}$).

Output

For each test case, output a single line contains a single integer, indicating the answer.

It can be proved that the answer always exists.

Examples

Input 1

3
1 10
1 100
1 1000

Output 1

3
4
942786340