#include<bits/stdc++.h>
#define MOD 1000000007
#define quick ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef long double ld;
vector<ll> fibs(1000);
int main()
{
ll t;
cin>>t;
fibs[1]=1;
for(ll i=2;i<fibs.size();i++)
fibs[i]=fibs[i-1]+fibs[i-2];
while(t--)
{
ll a,b;
cin>>a>>b;
cout<<fibs[__gcd(a,b)]<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBNT0QgMTAwMDAwMDAwNwojZGVmaW5lIHF1aWNrIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKE5VTEwpO2NvdXQudGllKE5VTEwpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwoKdmVjdG9yPGxsPiBmaWJzKDEwMDApOwppbnQgbWFpbigpCnsKCWxsIHQ7CgljaW4+PnQ7CglmaWJzWzFdPTE7Cglmb3IobGwgaT0yO2k8Zmlicy5zaXplKCk7aSsrKQoJCWZpYnNbaV09Zmlic1tpLTFdK2ZpYnNbaS0yXTsKCXdoaWxlKHQtLSkKCXsKCQlsbCBhLGI7CgkJY2luPj5hPj5iOwoJCWNvdXQ8PGZpYnNbX19nY2QoYSxiKV08PGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==