#462 Catwalk BrainF**k

Statement

Statement language

The esoteric programming language BrainF**k is written using only the eight characters +-][><,..

> : Increase the pointer by $1$ .
< : Decrease the pointer by $1$ .
+ : Increase the value at the current pointer by $1$ .
- : Decrease the value at the current pointer by $1$ .
. : Output the value at the current pointer as an ASCII character.
, : Read one character and overwrite the value at the current pointer with its ASCII code.
[ : If the byte at the current pointer is $0$ , jump to the matching ].
] : If the byte at the current pointer is not $0$ , jump to the matching [.

The characters [ and ] denote the beginning and end of loops. Compilation fails if and only if these brackets are not properly matched.

A cat walks on the keyboard. At every step, it types one uniformly random character from +-][><,..

Given an integer $N$ , find the probability that the length- $N$ string typed after exactly $N$ steps can be compiled as BrainF**k code.

Input

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

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the answer on one line.

Write the probability for that test case as a reduced fraction $\cfrac{p}{q}$ . The denominator $q$ is not divisible by $998\,244\,353$ . Let be the multiplicative inverse of modulo . Print

Constraints

$1 \le T \le 200\,000$ .
$1 \le N \le 100\,000$ .

Subtasks

#	Score	Constraints
1	24	$N \le 2\,000$ .
2	31	$T \le 5$ .
3	45	No additional constraints.

Samples

Input

Output

For the first test case, the program compiles exactly when one of the six non-bracket characters is typed. The probability is $\cfrac{6}{8}=\cfrac{3}{4}$ , which is modulo .