#include <bits/stdc++.h>

#define llong long long

using namespace std;

typedef vector<int> big;

const int MAXN = (int) 1e6 + 7;
const int INF = (int) 1e9 + 23;

int plen = 1490280;

int bin(int x, long long y) {
  int res = 1;
  while (y > 0) {
    if (y & 1LL) res = (1ll * res * x) % INF;
    y >>= 1LL;
    x = (1ll * x * x) % INF;
  }
  return res;
}

int phi(int x) {
  int res = x;
  for (int i = 2; i * i  <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      res -= res / i;
    }
  }
  if (x > 1)
    res -= res / x;

  return res;
}

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

  int t, n;
  int cur, prv, blocks, ans;

  long long k;

  scanf("%d", &t);
  while (t--) {
    scanf("%d%lld", &n, &k);

    k %= phi(INF);

    ans = 0;
    blocks = n / plen;

    cur = prv = 1;
    for (int i = 3; i <= plen; i++) {
      cur += prv;
      if (cur >= INF)
        cur -= INF;

      prv = cur - prv;
      if (prv < 0)
        prv += INF;

      ans += bin(cur, k);
      if (ans >= INF)
        ans -= INF;
    }
    ans += 2;
    if (ans >= INF)
      ans -= INF;

    ans = (1LL * ans * blocks) % INF;

    n -= blocks * plen;

    cur = prv = 1;
    for (int i = 3; i <= n; i++) {
      cur += prv;
      if (cur >= INF)
        cur -= INF;

      prv = cur - prv;
      if (prv < 0)
        prv += INF;

      ans += bin(cur, k);
      if (ans >= INF)
        ans -= INF;
    }
    if (n >= 1) ans++;
    if (n >= 2) ans++;

    if (ans >= INF)
      ans -= INF;

    printf("%d\n", ans);
  }
  return 0;
}