Problem Statement

You are given integers $N$ and $P$.

There is a graph with $N$ vertices and $N$ edges, where each vertex is labeled $1$ to $N$. The $i$-th edge connects vertices $i$ and $i+1$ bidirectionally. Here, vertex $N+1$ refers to vertex $1$.

Perform the following algorithm to obtain a sequence $D=(D_1,D_2,\ldots,D_N)$ of length $N$:

• Set an integer sequence $D$ of length $N$ to $D=(D_1,\ldots,D_N)=(-1,\ldots,-1)$. Also, set a sequence $Q$ of number pairs to $Q=((1,0))$. Repeat the following process while $Q$ is not empty:
• Let $(v,d)$ be the first element of $Q$. Remove this element.
  • If $D_v = -1$, then set $D_v := d$, and for each vertex $x$ adjacent to vertex $v$ such that $D_x=-1$, perform the following process. If there are multiple such $x$ that satisfy the condition, process them in ascending order of vertex number:
  • With probability $\frac{P}{100}$, add $(x,d+1)$ to the front of $Q$.
    • If $(x,d+1)$ was not added to the front of $Q$, add it to the end of $Q$.

Find the expected value of the sum of the elements of the final sequence $D$ obtained, modulo $998244353$.

Solve each of the $T$ test cases given.

Definition of expected value $\text{mod } 998244353$ It can be proved that the expected value to be found is always a rational number. Furthermore, the constraints of this problem guarantee that if that value is expressed as an irreducible fraction $\frac{P}{Q}$, then $Q$ is not divisible by $998244353$. Here, there is a unique integer $R$ between $0$ and $998244352$, inclusive, such that $R\times Q \equiv P\pmod{998244353}$. Provide this $R$ as the answer.

Constraints

• $1 \leq T \leq 10^4$
• $3 \leq N \leq 10^{18}$
• $1\leq P \leq 99$
• All input numbers are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N P

Output

Print $T$ lines. The $i$-th line $(1 \leq i \leq T)$ should contain the answer for the $i$-th test case.