#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define f first
#define s second

#define pii pair<int, int>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 7;
const int MAXN = (int) 5e4 + 7;

int tests;
int n, banned;

int dp[MAXN][1 << 4][2];
int ways[MAXN][1 << 4][2];

void add(int &x, int y) {
  x += y;
  if (x >= INF)
    x -= INF;
}

int main() {
  #ifdef LOCAL
  freopen("in", "r", stdin);
  #endif // LOCAL

  scanf("%d", &tests);
  while (tests--) {
    scanf("%d%d", &n, &banned);
    for (int mask = 0; mask < 16; mask++) {
      vector<int> arr;
      for (int i = 0; i < 4; i++)
        arr.pb((mask >> i) & 1);
      reverse(arr.begin(), arr.end());
      int sum = 0, ptr = 0;
      while (ptr < 4) {
        sum += arr[ptr] + 1;
        if (arr[ptr]) ptr += 2;
        else ptr++;
      }
      dp[4][mask][ptr == 4] += sum;
      ways[4][mask][ptr == 4]++;
    }
    for (int len = 4; len < n; len++) {
      for (int mask = 0; mask < 16; mask++) {
        for (int take = 0; take < 2; take++) {
          int sum = 0;
          for (int i = 0; i < 4; i++)
            sum += ((mask >> i) & 1) + 1;
          if (sum + 1 != banned) {
            // place 1
            int nmask = (mask & 7) << 1;
            if (take) {
              add(ways[len + 1][nmask][take], ways[len][mask][take]);
              add(dp[len + 1][nmask][take], dp[len][mask][take]);
              add(dp[len + 1][nmask][take], ways[len][mask][take]);
            } else {
              add(ways[len + 1][nmask][1], ways[len][mask][take]);
              add(dp[len + 1][nmask][1], dp[len][mask][take]);
            }
          }
          if (sum + 2 != banned) {
            // place 2
            int nmask = (mask & 7) << 1;
            ++nmask;
            if (take) {
              add(ways[len + 1][nmask][0], ways[len][mask][take]);
              add(dp[len + 1][nmask][0], dp[len][mask][take]);
              add(dp[len + 1][nmask][0], ways[len][mask][take]);
              add(dp[len + 1][nmask][0], ways[len][mask][take]);
            } else {
              add(ways[len + 1][nmask][1], ways[len][mask][take]);
              add(dp[len + 1][nmask][1], dp[len][mask][take]);
            }
          }
        }
      }
    }
    int ans = 0, all = 0;
    for (int mask = 0; mask < 16; mask++)
      for (int take = 0; take < 2; take++)
        add(ans, dp[n][mask][take]);
    printf("%d\n", ans);
    for (int i = 0; i <= n; i++)
      for (int mask = 0; mask < 16; mask++)
        for (int take = 0; take < 2; take++)
          dp[i][mask][take] = ways[i][mask][take] = 0;
  }

  return 0;
}