#include<cstdio>
#include<iostream>
#include<climits>
using namespace std;
typedef long long ll;
const ll di=1000000007;
ll arr[100009];
int main(){
    ll a,b,c,d,e,f,g,h,n,k;
    ios::sync_with_stdio(false);
            d=(k+1)/2;
            d*=k;
    cin>>b;
    //freopen("out","w",stdout);
    //printf("%llu %lld\n",1000000000*1000000001,LLONG_MAX);
    while(b--){
        cin>>n>>k;
        if(k%2){
            d=(k+1)/2;
            d*=k;
        }
        else {
            d=k/2;
            d*=(k+1);
        }
        //printf("%lld\n",d);
        ll tmp=-1;
        if(n<d||k>=100000){
            cout<<tmp<<endl;
            continue;
        }
        f=n/k;
        d=(k+1)/2;
        if(k%2)d--;
        arr[d]=f;
        //printf("%d %d\n",f,d);
        for(int i=d-1;i>-1;i--){
            arr[i]=arr[i+1]-1;
        }
        for(int i=d+1;i<k;i++){
            arr[i]=arr[i-1]+1;
        }
        //for(d=0;d<k;d++)printf("%lld ",arr[d]);printf("\n");
        ll tt=2;
        if(k%2)e=n-k*f;
        else e=n-k*(arr[0]+arr[k-1])/tt;
        //printf("%d\n",e);
        for(d=0;e<0&&d<k;d++){
            arr[d]--;
            e++;
        }
        for(d=k-1;e&&d>=0;d--){
            arr[d]++;
            e--;
        }
        for(d=k-1;e&&d>=0;d--){
            arr[d]++;
            e--;
        }
        for(g=1,d=0;d<k;d++){
            g*=arr[d];
            g%=di;
            //printf("%lld %lld\n",arr[d],g);
        }
        //for(d=0;d<k;d++)printf("%d ",arr[d]);printf("\n");
        cout<<g%di<<endl;
    }
    return 0;
}