#596 Easy Sequence Problem

Statement

Statement language

There is an infinite sequence $A$ . We have $A_0=0$ , $A_1=1$ , and for every nonnegative integer $k$ ,

$A_{2k}=A_k$ ,
$A_{2k+1}=A_k+A_{k+1}$ .

You are given two coprime positive integers $P,Q$ . It is guaranteed that there exists a unique positive integer $N$ satisfying $(A_N,A_{N+1})=(P,Q)$ .

Find $N$ modulo $998\,244\,353$ .

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 corresponding $N$ modulo $998\,244\,353$ .

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq P,Q \leq 10^{18}$ .

Subtasks

#	Score	Constraints
1	13	$P,Q \leq 100$ .
2	21	$\min(P,Q)=1$ .
3	66	No additional constraints.

Samples

Input

Output

1
5
6

The first several terms of the sequence are

0,1,1,2,1,3,2,3.

Therefore, the values of $N$ satisfying the condition in the three test cases are $1, 5,$ , respectively.