//#ifdef DEBUG
//#define _GLIBCXX_DEBUG
//#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
ll dp[102][102];
const int maxP = 1e6 + 10;
int nxt[maxP][2];
int SZ = 0;
map<pair<vector<int>, int>, int> mp;
pair<vector<int>, int> bck[maxP];

int get_id(const pair<vector<int>, int> &T) {
    if (mp.count(T)) {
        return mp[T];
    }
    mp[T] = SZ;
    bck[SZ] = T;
    SZ++;
    assert(SZ < 1000'000);
    return SZ - 1;
}

int dist[maxP];

void init() {
    int n = 50;
    pair<vector<int>, int> st = make_pair(vector<int>(), 0);
    assert(get_id(st) == 0);
    queue<int> q;
    q.push(0);
    memset(dist, -1, sizeof dist);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int c = 1; c <= 2; c++) {
            auto ns = bck[v];
            auto X = ns.first;
            auto Y = ns.second;
            X.emplace_back(c);
            Y += c;
            while (X.size() >= 3 && X[X.size() - 3] <= X[X.size() - 2] && X[X.size() - 2] >= X[X.size() - 1]) {
                X[X.size() - 3] -= X[X.size() - 2];
                X[X.size() - 3] += X.back();
                X.pop_back();
                X.pop_back();
            }
            nxt[v][c - 1] = get_id(make_pair(X, Y));
            if (dist[nxt[v][c - 1]] == -1) {
                dist[nxt[v][c - 1]] = dist[v] + 1;
                if (dist[nxt[v][c - 1]] < n) {
                    q.push(nxt[v][c - 1]);
                }
            }
        }
    }
}

ll val[maxP];
ll nval[maxP];

void solve() {
    int n, q;
    cin >> n >> q;
//    n = 50;
//    q = 0;
    string s = string(n, '?');
    cin >> s;
    for (int j = 0; j < SZ; j++) {
        val[j] = 0;
    }
    val[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < SZ; j++) nval[j] = 0;
        for (int j = 0; j < SZ; j++) {
            if (val[j] == 0) continue;
            for (int c = 0; c < 2; c++) {
                if (s[i] == (char) (2 - c + '0')) continue;
                nval[nxt[j][c]] += val[j];
            }
        }
        for (int j = 0; j < SZ; j++) {
            val[j] = nval[j];
        }
    }
    //    map<pair<vector<int>,int>,ll> mp;
    //    mp[{{}, 0}] = 1;
    //    int sz = 0;
    //    for (char& c : s) {
    //        map<pair<vector<int>,int>,ll> nmp;
    //        for (auto& it : mp) {
    //            for (int z = 1; z <= 2; z++) {
    //                if (c == (char)(3 - z + '0')) continue;
    //                auto nit = it;
    //                auto X = nit.first.first;
    //                auto Y = nit.first.second;
    //                X.emplace_back(z);
    //                Y += z;
    //                while (X.size() >= 3 && X[X.size() - 3] <= X[X.size() - 2] && X[X.size() - 2] >= X[X.size() - 1]) {
    //                    X[X.size() - 3] -= X[X.size() - 2];
    //                    X[X.size() - 3] += X.back();
    //                    X.pop_back();
    //                    X.pop_back();
    //                }
    //                nmp[{X, Y}] += it.second;
    //            }
    //        }
    //        ++sz;
    //        swap(mp, nmp);
    //        cout << mp.size() << " ? " << sz << endl;
    //    }
    //    return ;
    memset(dp, 0, sizeof dp);
    for (int j = 0; j < SZ; j++) {
        if (val[j] == 0) continue;
        int S = bck[j].second;
        auto vec = bck[j].first;
        int bal = 0;
        int fl = 0;
        while (!vec.empty()) {
            int x = 0;
            if (vec[0] >= vec.back()) {
                x = vec[0];
                vec.erase(vec.begin());
            } else {
                x = vec.back();
                vec.pop_back();
            }
            if (!fl) bal += x;
            else bal -= x;
            fl ^= 1;
        }
        dp[(bal + S) / 2][(S - bal) / 2] += val[j];
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << dp[a][b] << '\n';
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    init();
    int tst = 1;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}