#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 10000
const LL mod=1e4;
LL sum[N];
LL T,a,b;
LL quickly_pow(LL a,LL p,LL mod){
	LL ans=1;
	while(p){
		if(p&1) ans=ans*a%mod;
		a=(a*a)%mod;
		p>>=1;
	}
	return ans%mod;
}
int main(){
	cin>>T;
	//cout<<T;
	//cout<<mod;
	//cout<<quickly_pow(2,3,3);
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=T;i++){
		cin>>a>>b;
		for(int j=1;j<=mod;j++){
			sum[j]=(sum[j-1]+quickly_pow(j,b,mod))%mod;
		}
		LL ans=(a/mod*sum[mod]+sum[a%mod])%mod;
		cout<<ans<<endl;
		//cout<<i<<endl;
	}
	return 0;
}

全部都WA了！ 有谁来帮帮蒟蒻！！！