E. A Counting Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Find the number of $$$x$$$ satisfied the following condition:

  • $$$x \in [0, 10^n)$$$
  • $$$2^a \times 3 \mid x$$$
Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10000$$$) — the number of testcases. Each testcase contains two integers $$$n$$$ and $$$a$$$ in a line. ($$$1 \leq a \leq n \leq 10^{18}$$$)

Output

For each testcase, print the number of $$$x$$$ satisfied the given conditions in a single line. Since the answer can be large, print it modulo $$$998244353$$$.

Example
Input
1
1 1
Output
2