#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int prime[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
 
int mask[102];
int dp[102][1 << 15];
 
long long fa[111111];
long long pfa[111111];
 
#define next next_
const int md = 1000000007;
 
long long poww(long long a, long long b){
    long long ans = 1;
    while (b){
        if (b % 2 == 1){
            ans = (ans * a) % md;
        }
        a = (a * a) % md;
        b /= 2;
    }
    return ans;
}
 
void add(int &v, int val){
    v += val;
    if (v >= md) v -= md;
}
 
long long cnk(int n, int k){
    return fa[n] * pfa[n - k] % md * pfa[k] % md;
}
long long ank(int n, int k){
    return fa[n] * pfa[n - k] % md;
}
 
int main(){
    //freopen("03.tst", "r", stdin);
    //freopen("03.ans", "w", stdout);
 
    fa[0] = 1;
    pfa[0] = 1;
    for (int i = 1; i <= 100000; i++){
        fa[i] = (fa[i - 1] * i) % md;
        pfa[i] = poww(fa[i], md - 2);
    }
 
    for (int i = 1; i <= 100; i++){
        mask[i] = 0;
        for (int j = 0; j < 15; j++){
            if (i % prime[j] == 0) mask[i] ^= (1 << j);
        }
    }
 
    int T;
    cin >> T;
    while (T){
        T--;
        int n, m;
        cin >> n >> m;      
        int C = 0;
        for (int i = 15; i < 25; i++){
            if (prime[i] <= m) C++;
        }
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;       
        long long ans = 0;
        for (int i = 0; i <= m; i++){       
            if (i > n) {
                break;
            }     
            int tot = 0;
            for (int pmask = 0; pmask < (1 << 15); pmask++){
                add(tot, dp[i][pmask]);
                for (int next = 2; next <= m; next++){
                    if ((pmask & mask[next]) == 0 && mask[next] != 0){
                        add(dp[i + 1][pmask ^ (mask[next])], dp[i][pmask]);                        
                    }
                }
              
            }
            long long temp = cnk(n, i) * tot % md;            
            for (int big = 0; big <= min(n - i, C); big++){
                ans = (ans + temp * cnk(n - i, big) % md * ank(C, big)) % md;
            }            
        }
        cout << ans << endl;
    }
 
    return 0;
}