(快速幂你做了什么？？？)

#include<bits/stdc++.h>
using namespace std;
inline long long qpow(long long a,long long p,long long mod){
	long long sum=1;
	while(p){
		if(p&1){
			sum=sum*a%mod;
		}
		a=a*a%mod;
		p>>=1;
	}
	return sum%mod;
}
int main(){
	int a,b,ans[10001]={0};
	int n;
	cin>>n;
	for(int j=1;j<=n;j++){
		cin>>a>>b;
		for(int i=1;i<=a;i++)ans[j]+=qpow(i,b,10000);
    	ans[j]%=10000;
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0; 
}