#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define ll long long
const int p = 998244353;
struct Matrix {
	int f[7][7];
}M0,M1;
const int N = 6;
ll A,B,G;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
Matrix mul( Matrix a , Matrix b ) {
	Matrix c;
	rep(i,1,N) rep(j,1,N) {
		c.f[i][j] = 0;
		rep(k,1,N) 
			c.f[i][j] = ( c.f[i][j] + ( 1ll*a.f[i][k]*b.f[k][j]%p ) ) %p;
	}
	return c;
}
Matrix pow( Matrix a , ll b ) {
	Matrix res;
	rep(i,1,N) rep(j,1,N) res.f[i][j] = (i==j);
	while(b) {
		if(b&1) res = mul( res , a );
		a = mul( a , a );
		b >>= 1;
	}
	return res;
}
Matrix get() {
	Matrix a;
	int AA[7][7] = 
			{{0, 0, 0, 0, 0, 0, 0},
			{0, 1, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0},
			{0, 1, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0}};
	for(int i=1;i<=6;i++) for(int j=1;j<=6;j++) a.f[i][j] = AA[i][j];
	return a;
}
void solve(ll A,ll B,Matrix Ma,Matrix Mb) {
	// printf("*%lld %lld\n",A,B);
	// 	rep(i,1,N) {
	// 		rep(j,1,N)
	// 			printf("%d ",Ma.f[i][j]); printf("\n");
	// 	}
	// 	printf("\n");
	// 	rep(i,1,N) {
	// 		rep(j,1,N)
	// 			printf("%d ",Mb.f[i][j]); printf("\n");
	// 	}
	// 	printf("\n");


	if( B == 0 ) {
		Matrix zero = get();
		zero = mul( pow(Mb,G) , zero );
		printf("%d\n",((zero.f[1][1]+zero.f[3][1])%p+p)%p);
		return;
	}


	if( A <= B ) {
		solve( A , B%A , Ma , 
						mul( pow( Ma , B/A ) , Mb ) 
			);
	}
	else 
		solve( A - (A-1)/B*B , B , mul( pow( Mb , (A-1)/B ) , Ma ) 
								, Mb 
			);
}
#define g(a,i,j) a.f[i][j]
int main(){
	int T; scanf("%d",&T);
	while(T--) {
		scanf("%lld%lld",&A,&B);
		G = gcd(A,B);
		rep(i,1,N) rep(j,1,N) {
			M0.f[i][j] = 0;
			M1.f[i][j] = 0;
		}
		int AA[7][7] = {{0, 0, 0, 0, 0, 0, 0},
				{0, 2, -1, 1, 1, 0, 1},
				{0, 1, 0, 1, 0, 0, 0},
				{0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 1, 1},
				{0, 0, 0, 0, 0, 0, 0}};
		for(int i=1;i<=6;i++) for(int j=1;j<=6;j++) M0.f[i][j] = AA[i][j];
		int BB[7][7] = {{0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 0, 0},
				{0, 1, 1, 2, -1, 1, 0},
				{0, 1, 0, 1, 0, 0, 0},
				{0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 1, 1}};
		for(int i=1;i<=6;i++) for(int j=1;j<=6;j++) M1.f[i][j] = BB[i][j];
		// rep(i,1,N) {
		// 	rep(j,1,N)
		// 		printf("%d ",M0.f[i][j]); printf("\n");
		// }
		// printf("\n");
		// rep(i,1,N) {
		// 	rep(j,1,N)
		// 		printf("%d ",M1.f[i][j]); printf("\n");
		// }
		// printf("\n");
		solve(A,B,M0,M1);
	}
	return 0;
}