쉬운 수열 문제

크기가 무한한 수열 $A$가 있다. $A_0=0$, $A_1=1$이며, 모든 음이 아닌 정수 $k$에 대해 다음을 만족한다.

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

서로소인 두 양의 정수 $P,Q$가 주어진다. $(A_N,A_{N+1})=(P,Q)$를 만족하는 양의 정수 $N$은 유일하게 존재한다.

이 $N$을 $998\,244\,353$으로 나눈 나머지를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$P\ Q$

각 테스트 케이스마다 해당하는 $N$을 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

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