#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using uint=unsigned;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define si(x) int(x.size())
#define a first
#define b second
#define mp make_pair
template<class t>using vc=vector<t>;

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b; return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(a>b){a=b; return true;}else return false;}

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u> &p){
	return os<<"{"<<p.a<<","<<p.b<<"}"<<endl;
}

template<class t> ostream& operator<<(ostream& os,const vector<t>& v){
	os<<"{";
	for(auto e: v)os<<e<<",";
	return os<<"}";
}
#define mp make_pair
using P=pair<int,int>;
using V=vc<ll>;
template<class t>using vvc=vc<vc<t>>;
const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint&operator+=(mint r){return s(v+r.v);}
	mint&operator-=(mint r){return s(v+mod-r.v);}
	mint&operator*=(mint r){v=(unsigned long long)v*r.v%mod;return *this;}
	mint&operator/=(mint r){return *this*=r.inv();}
	mint operator+(mint r)const{return mint(*this)+=r;}
	mint operator-(mint r)const{return mint(*this)-=r;}
	mint operator*(mint r)const{return mint(*this)*=r;}
	mint operator/(mint r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0) return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1) res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};
vvc<mint>mul(vvc<mint>a,vvc<mint>b){
	int n = si(a), m = si(b[0]);
	vvc<mint>ret(n,vc<mint>(m,0));
	rep(i,n){
		rep(j,si(a[0])){
			rep(k,m){
				ret[i][k] += a[i][j] * b[j][k];
			}
		}
	}
	return ret;
}
vvc<mint>pow(vvc<mint>a,ll n){
	vvc<mint>res;
	while(n){
		if(n&1){
			if(res.empty()) res = a;
			else res = mul(res, a);
		}
		a = mul(a, a);
		n>>=1;
	}
	return res;
}
void solve(){
	ll a,b;cin>>a>>b;
	auto calc=[&](auto self,ll a,ll b,vvc<mint>X, vvc<mint>Y)->vvc<mint>{
		//cout << a << " " << b << " " << si(X) << " " << si(Y) << endl;
		if(a == 1){
			return mul(pow(Y, b), X);
		}
		else if(b == 1){
			return mul(mul(pow(X, a-1), Y), X);
		}
		else{
			if(a < b){
				return self(self,a,b%a,mul(pow(Y,b/a),X), Y);
			}
			else{
				return self(self,a%b,b,X,mul(pow(X,a/b),Y));
			}
		}
	};
	vvc<mint>z(3,vc<mint>(3,0));
	vvc<mint>o(3,vc<mint>(3,0));
	z[0][0] = z[0][1] = z[0][2] = z[1][1] = z[2][2] = 1;
	o[0][0] = o[1][0] = o[1][1] = o[1][2] = o[2][2] = 1;
	ll g = gcd(a,b);
	auto ret = calc(calc,a/g,b/g,z,o);
	ret = pow(ret, g);
	mint ans;
	rep(i,3) ans += ret[i][2];
	cout << ans.v << '\n';
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t;cin>>t;
	while(t--) solve();
}