#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
//#define int ll

const int MOD=998244353;

#if 1
using row=array<int,3>;
using matr=array<row,3>;
const matr ONE={
    row{1,0,0},
    row{0,1,0},
    row{0,0,1}
};
matr mul(matr l,matr r)
{
    matr res{};
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; j++)
        {
            res[i][j]=((ll)l[i][0]*r[0][j]+(ll)l[i][1]*r[1][j]+(ll)l[i][2]*r[2][j])%MOD;
        }
    return res;
}
const matr X={
    row{1,0,0},
    row{1,1,0},
    row{1,0,1}
};
const matr Y={
    row{1,1,0},
    row{0,1,0},
    row{0,1,1}
};
const matr invX={
        row{1,0,0},
        row{MOD-1,1,0},
        row{MOD-1,0,1}
};
const matr invY={
        row{1,MOD-1,0},
        row{0,1,0},
        row{0,MOD-1,1}
};
auto ret(matr res)
{
    return (res[2][0]+res[2][1]+1)%MOD;
}
#else
using matr=string;
const matr ONE;
matr mul(const matr& l,const matr& r)
{
    return l+r;
}
const matr X="1";
const matr Y="0";
auto ret(matr res)
{
    return res;
}
#endif

matr pow(matr x,int y)
{
    matr res=ONE;
    while(y)
    {
        if(y&1)
            res=mul(res,x);
        y>>=1;
        x=mul(x,x);
    }
    return res;
}

matr rec(ll a, ll b, matr x, matr y)
{
    while(a>1||b>1)
    {
//        cout << a << " " << b << " " << x << " " << y << "\n";
        matr xx=mul(pow(x, b / a - 1),y);
        matr yy=mul(x,xx);
        tie(a, b, y, x)=tuple(a - b % a, a, xx, yy);
    }
    return y;
}

auto solve(ll a,ll b)
{
    ll g=__gcd(a,b);
    bool sw=a>b;
    if(sw)
        swap(a,b);
    matr res=rec(a/g,b/g,Y,mul(X,Y));
    if(!sw)
    {
        res=mul(res,invY);
        res=mul(res,invX);
        res=mul(res,Y);
        res=mul(res,X);
    }
    res=pow(res,g);
    return ret(res);
}

std::string gen_string(int64_t a, int64_t b) {
    std::string res;
    int64_t ia = 0, ib = 0;
    while (ia + ib < a + b) {
        if ((__int128)ia * b <= (__int128)ib * a) {
            res += '0';
            ia++;
        } else {
            res += '1';
            ib++;
        }
    }
    reverse(res.begin(),res.end());
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    while(t--)
    {
        ll a,b;
        cin>>a>>b;
//        cout<<gen_string(a,b)<<"\n";
        cout<<solve(a,b)<<"\n";
    }
}