#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <iomanip>
#include <stdexcept>
#include <utility>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
#define MOD 1000007


void factorial(vector<ll>& dp, int n) {
    dp[0] = 1;

    for(int i = 1; i<n; i++) {
        dp[i] = i* dp[i-1];
    }
}

int nCr(vector<ll>& dp, int n, int r) {
    return dp[n] / (dp[r] * dp[(n - r)]);
}


ll gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

void FastDoubling (ll n, ll res[]) {
    ll a, b, c, d;
    // Base Condition
    if (n == 0) {
        res[0] = 0;
        res[1] = 1;
        return;
    }
    FastDoubling((n / 2), res);
 
    // Here a = F(n)
    a = res[0];
 
    // Here b = F(n+1)
    b = res[1];
 
    c = 2 * b - a;
 
    if (c < 0)
        c += MOD;
 
    // As F(2n) = F(n)[2F(n+1) – F(n)]
    // Here c  = F(2n)
    c = (a * c) % MOD;
 
    // As F(2n + 1) = F(n)^2 + F(n+1)^2
    // Here d = F(2n + 1)
    d = (a * a + b * b) % MOD;
 
    // Check if N is odd
    // or even
    if (n % 2 == 0) {
        res[0] = c;
        res[1] = d;
    }
    else {
        res[0] = d;
        res[1] = c + d;
    }
}



int main()
{
    // these first two lines speed up input / output significantly
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll p;

    cin>>p;

    while(p--){
        ll k, s;

        cin>>k;
        cin>>s;

        ll sum = 0;

        ll t;
        ll o;

        if(s%4 == 0) {
            t = s/4;
            o = 0;
        } else {
            t = s/4;
            o = 1;
        }

        vector<ll> factorial_dp(s/2);
        factorial(factorial_dp, s/2);

        if(s == 2) {
            cout<<k<<" 0"<<"\n";
        } else {
            while(t >= o) {
                ll comb = nCr(factorial_dp, (t+o), t);
                sum += comb*comb;
                o+=2;
                t--;
            }
        }
        
        cout<<k<<" "<<sum<<"\n";

    }                                                                                                                           

}