F. Nesr El Sieve

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e6+5;
const ll INF=1e18;
const ll MOD=998244353;

ll N;
string s1,s2;

ll gcd(ll a,ll b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
void init(){
    cin>>s1>>s2;
    cout<<gcd((ll)s1.size(),(ll)s2.size())<<'\n';
}

signed main(){
    fastio
    freopen("sieve.in","r",stdin);
    ll T;
    cin>>T;
    while(T--){
        init();
    }
    return 0;
}