Easy Sequence Problem

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$.

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

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

Each case is given in the following format:

$P\ Q$

For each test case, print the corresponding $N$ modulo $998\,244\,353$.

• $1 \leq T \leq 200\,000$.
• $1 \leq P,Q \leq 10^{18}$.
• $\gcd(P,Q)=1$.