#include<stdio.h>

int main(){
    long long o,t,n,k,tich,tich2,gom;
    scanf("%lld", &t);
    for(int i=1;i<=t;i++){
        tich=1;
        tich2=1;
        gom=1;
        scanf("%lld %lld", &n,&k);
        for(int i=1;i<=n;i++){
            tich=tich*(k-1);
        }
        o=0-1;
        for(int i=1;i<=n;i++){
            tich2=tich2*o;
        }
        gom=tich+(k-1)*tich2;
        gom=gom%6971;
        printf("%lld ", gom);
    }
}