#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
#define int long long


int p;

int potega(int a, int k, int q){
    if (k==0)
        return 1;
    if (k%2==0){
        int  w=potega(a,k/2,q);
        return (w*w)%q;
    }
    int w=potega(a,k-1,q);
    return (a*w)%q;

}

vector<int> eval(vector<int>A, int x){
    vector<int> wynik;
    if(A.size()==1){
        wynik.push_back(A[0]);
        return wynik;
    }
    vector<int> A0;
    vector<int> A1;
    for(int i=0; i<A.size(); i++){
        if(i%2==0){
            A0.push_back(A[i]);
        }else{
            A1.push_back(A[i]);
        }
    }
    vector<int> A0_wynik=eval(A0,(x*x)%p);
    vector<int> A1_wynik=eval(A1,(x*x)%p);

    int om=1;
    for(int i=0; i<A.size()/2; i++){
        int temp=(A0_wynik[i]+(om*A1_wynik[i])%p)%p;
        wynik.push_back(temp%p);
        if(i>0){
            om*=x;
            om%=p;
        }
        else
            om=x;
    }
    om=1;
    for(int i=0; i<A.size()/2; i++){
        int temp=(A0_wynik[i]-(om*A1_wynik[i])%p+p)%p;
        wynik.push_back(temp%p);
        if(i>0){
            om*=x;
            om%=p;
        }
        else
            om=x;
    }
    return wynik;

}

#undef int
int main(){
#define int long long

    p=1;
    for(int i=0; i<27; i++)
        p*=2;
    p*=15;
    p+=1;

    int z;
    cin>>z;
    while(z--){
        string a,b;
        cin>>a>>b;
        vector<int>A;
        vector<int>B;


        int znak=1;

        int poczatek=0;
        if(a[0]=='-'){
            poczatek++;
            znak*=-1;
        }
        for(int i=a.length()-1; i>=poczatek; i--){
            A.push_back(a[i]-'0');
        }

        poczatek=0;
        if(b[0]=='-'){
            poczatek++;
            znak*=-1;
        }
        for(int i=b.length()-1; i>=poczatek; i--){
            B.push_back(b[i]-'0');
        }


        int n=1;
        int ilecyfr=max(2*A.size(),2*B.size());
        while(n<ilecyfr)
            n*=2;


        for(int i=A.size(); i<n; i++){
            A.push_back(0);
        }
        for(int i=B.size(); i<n; i++){
            B.push_back(0);
        }


        int temp=1;
        for(int i=0; i<27; i++)
            temp*=2;
        temp/=n;
        int omega=440564289;
        omega=potega(omega,temp,p);



        vector<int> wartA=eval(A, omega);
        vector<int> wartB=eval(B,omega);



        for(int i=0; i<n; i++){
            wartA[i]=(wartA[i]*wartB[i])%p;
        }

        vector<int>wynik=eval(wartA,1 * potega(omega, p-2, p));


        temp=wynik.size();
        temp=potega(n,p-2,p);

        for(int i=0; i<wynik.size(); i++){
            wynik[i]*=temp;
            wynik[i]%=p;
        }
        for(int i=0; i<wynik.size()-1; i++){
            int x=wynik[i];
            wynik[i]%=10;
            wynik[i+1]+=x/10;
        }

        if(znak==-1)
            cout<<'-';

        bool omijajzera=true;
        for(int i=wynik.size()-1; i>=0; i--){
            if(omijajzera && wynik[i]==0)
                continue;
            else
                omijajzera=false;
            cout<<wynik[i];
        }
        cout<<endl;

    }
}