#include<stdio.h>
#define MM 1000000007
long ppow(int x, int a) {
    if (a == 0) return 1;
    if (a%2 > 0) return (ppow(x, a-1)*x) % MM;
    long half = ppow(x, a/2) % MM;
    return (half * half) % MM;
}
int main() {
    int cases;
    scanf("%d", &cases);
    while(cases--) {
        int n, m;
        scanf("%d %d", &n, &m);

        long sum[n+1];
        int i, j;
        for (i = 1; i <= n; i++) {
            sum[i] = ppow(n/i, m);
            sum[i] %= MM;
        }
        for (i = n/2; i > 0; i--) {
            for (j = 2; i*j <= n; j++) {
                sum[i] -= sum[i*j];
                sum[i] %= MM;
                if (sum[i] <= 0) sum[i] += MM;
            }
        }
        long S = 0;
        for (i = 1; i <= n; i++) {
            S += sum[i]*i;
            S %= MM;
        }
        printf("%ld\n", S);
    }
}