using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var prime = Enumerable.Repeat(true, 10_000_001).ToArray();
        prime[0] = false;
        prime[1] = false;
        for (var i = 2; i < prime.Length; ++i)
        {
            if (!prime[i]) continue;
            for (var j = i * 2; j < prime.Length; j += i) prime[j] = false;
        }
        var pcount = new int[prime.Length];
        for (var i = 2; i < prime.Length; ++i) pcount[i] = pcount[i - 1] + (prime[i] ? 1 : 0);
        var a2 = new int[prime.Length];
        for (var i = 5; i < prime.Length; ++i)
        {
            a2[i] = a2[i - 1];
            if ((i ^ 2) < i && prime[i] && prime[i - 2]) a2[i] += 2;
        }
        var t = NN;
        var ans = new long[t];
        for (var u = 0; u < t; ++u)
        {
            var c = NList;
            var (n, m) = (c[0], c[1]);
            ans[u] = Fold(n, m, pcount, a2);
        }
        WriteLine(string.Join("\n", ans));
    }
    static long Fold(int n, int m, int[] pcount, int[] a2)
    {
        if (n == 1) return pcount[m];
        if (m < 7) return 0;
        var a = new long[][] { new long[] { 1, a2[m] }};
        var x = new long[][]
        {
            new long[] { 0, a2[m] },
            new long[] { 1, 1 }
        };
        var b = Mul(a, Pow(x, n - 1));
        return (b[0][0] + b[0][1]) % mod;
    }
    static long Exp(long n, long p, int mod)
    {
        long _n = n % mod;
        var _p = p;
        var result = 1L;
        if ((_p & 1) == 1) result *= _n;
        while (_p > 0)
        {
            _n = _n * _n % mod;
            _p >>= 1;
            if ((_p & 1) == 1) result = result * _n % mod;
        }
        return result;
    }
    static int mod = 998_244_353;
    // 行列の累乗
    static long[][] Pow(long[][] m, long k)
    {
        var multi = m;
        var r = new long[m.Length][];
        for (var i = 0; i < m.Length; ++i)
        {
            r[i] = new long[m.Length];
            r[i][i] = 1;
        }
        while (k > 0)
        {
            if ((k & 1) == 1) r = Mul(r, multi);
            multi = Mul(multi, multi);
            k >>= 1;
        }
        return r;
    }
    // 行列の積
    static long[][] Mul(long[][] x, long[][] y)
    {
        var r = new long[x.Length][];
        for (var i = 0; i < x.Length; ++i) r[i] = new long[y[0].Length];
        for (var i = 0; i < x.Length; ++i) for (var k = 0; k < x[0].Length; ++k)
        {
            for (var j = 0; j < y[0].Length; ++j) r[i][j] = (r[i][j] + x[i][k] * y[k][j]) % mod;
        }
        return r;
    }
}