#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

struct mll {
    static const int MOD = 1e9 + 9;
    static vector<mll> inv_cache;
    static vector<mll> pow2, ipow2, fact, ifact;

    ll val;
    mll(ll _val = 0) {
        val = _val % MOD;
        if (val < 0) val += MOD;
    }

    #define def(op) \
        mll operator op (const mll &o) const { \
            return mll(val op o.val); \
        }
    def(+) def(-) def(*)

    mll pow(ll e) const {
        if (e == 0) return mll(1);
        if (e & 1) return *this * this->pow(e - 1);
        return (*this * *this).pow(e/2);
    }

    mll inv() const {
        assert(val != 0);
        if (val < inv_cache.size())
            return inv_cache[val];
        return this->pow(MOD - 2);
    }

    mll operator / (const mll &o) const {
        return *this * o.inv();
    }

    static mll ncr(int n, int r) {
        if (r < 0 || r > n) return mll(0);
        return fact[n] * ifact[r] * ifact[n-r];
    }

    static void init(int mval) {
        inv_cache.resize(mval);
        inv_cache[1] = mll(1);
        for (int i = 2; i < mval; i++)
            inv_cache[i] = inv_cache[MOD % i] * mll(-(MOD/i));

        pow2.resize(mval), ipow2.resize(mval);
        pow2[0] = ipow2[0] = mll(0);
        fact.resize(mval), ifact.resize(mval);
        fact[0] = ifact[0] = mll(1);

        for (int i = 1; i < mval; i++) {
            pow2[i] = pow2[i-1] * 2;
            ipow2[i] = ipow2[i-1] * inv_cache[2];
            fact[i] = fact[i-1] * i;
            ifact[i] = ifact[i-1] * inv_cache[i];
        }
    }

    friend ostream& operator<<(ostream &os, mll m) {
        return os << m.val;
    }
};
vector<mll> mll::inv_cache;
vector<mll> mll::pow2, mll::ipow2, mll::fact, mll::ifact;

template<typename T> struct matrix {
    int N;
    vector<T> dat;

    matrix<T> (int _N, T fill = T(0), T diag = T(0)) {
        N = _N;
        dat.resize(N * N, fill);

        for (int i = 0; i < N; i++)
            (*this)(i, i) = diag;
    }

    T& operator()(int i, int j) {
        return dat[N * i + j];
    }

    matrix<T> operator *(matrix<T> &b){
        matrix<T> r(N);

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                for(int k=0; k<N; k++)
                    r(i, j) = r(i, j) + (*this)(i, k) * b(k, j);

        return r;
    }

    matrix<T> pow(ll expo){
        if(!expo) return matrix<T>(N, T(0), T(1));
        matrix<T> r = (*this * *this).pow(expo/2);
        return expo&1 ? r * *this : r;
    }

    friend ostream& operator<<(ostream &os, matrix<T> &m){
        os << "{";
        for(int i=0; i<m.N; i++){
            if(i) os << "},\n ";
            os << "{";
            for(int j=0; j<m.N; j++){
                if(j) os << ", ";
                os << setw(10) << m(i, j) << setw(0);
            }
        }
        return os << "}}";
    }
};

vector<vector<bool>> read(int M, int state) {
    vector<vector<bool>> board(M, vector<bool>(2, false));
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 2; j++)
            board[i][j] = (state >> (2 * i + j))&1;
    }
    return board;
}

const int moves[8][2] = { { 1, 2 }, {1, -2}, {-1, 2}, {-1, -2},
                          { 2, 1 }, {2, -1}, {-2, 1}, {-2, -1} };

bool valid(int M, vector<vector<bool>> &board) {
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 3; j++) {
            if (!board[i][j]) continue;
            for (int m = 0; m < 8; m++) {
                int ii = i + moves[m][0];
                int jj = j + moves[m][1];
                if (ii < 0 || jj < 0 || ii >= M || jj >= 3) continue;
                if (board[ii][jj]) return false;
            }
        }
    }
    return true;
}

bool adj(int M, int s1, int s2) {
    auto b1 = read(M, s1);
    auto b2 = read(M, s2);

    for (int i = 0; i < M; i++) {
        if (b2[i][0] != b1[i][1])
            return false;
    }

    vector<vector<bool>> comb(M, vector<bool>(3));
    for (int i = 0; i < M; i++) {
        comb[i][0] = b1[i][0];
        comb[i][1] = b1[i][1];
        comb[i][2] = b2[i][1];
    }

    return valid(M, comb);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int M, N;
        cin >> M >> N;

        int states = 1 << (2 * M);

        matrix<mll> m(states, 0, 0);

        for (int s1 = 0; s1 < states; s1++) {
            for (int s2 = 0; s2 < states; s2++) {
                if (adj(M, s1, s2))
                    m(s1, s2) = m(s1, s2) + 1;
            }
        }

        m = m.pow(N + 2);
        cout << m(0, 0) << "\n";
    }

    return 0;
}