#655 Sorting a Sequence

Statement

Statement language

A prime is an integer greater than $1$ whose only positive divisors are $1$ and itself. A composite is an integer greater than $1$ that is not prime. The integer $1$ is neither prime nor composite.

Define the sequences $P$ and $C$ as follows.

$P_i$ is the $i$ -th smallest prime.
$C_i$ is the $i$ -th smallest composite.

The first five terms of $P$ are $2,3,5,7,11$ , and the first five terms of $C$ are $4,6,8,9,10$ .

Append the first $N$ terms of $C$ to the first $N$ terms of $P$ to form a sequence $X$ of length $2N$ . In other words,

X=(P_1,P_2,\ldots,P_N,C_1,C_2,\ldots,C_N).

Find the $K$ -th smallest number in $X$ . Since the answer may be large, output its remainder when divided by $998\ 244\ 353$ .

Input

The input is given in the following format.

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

Output

For each test case, output the remainder when the $K$ -th smallest number in $X$ is divided by $998\ 244\ 353$ , on a separate line. Output the answers in the order the test cases appear in the input.

Constraints

$1 \leq T \leq 100\ 000$ .
$1 \leq K \leq N \leq 10^{18}$ .

Subtasks

#	Score	Constraints
1	23	$N \leq 100$ .
2	77	No additional constraints.

Samples

Input

Output

2
4
3

In the first test case, $X=(2,4)$ , so the smallest number is $2$ .

In the second test case, $X=(2,3,5,4,6,8)$ . Sorting it in ascending order gives , so the third smallest number is .