#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a,b,s[100];
    cin>>n;
    for(int i=0;i<n;i++){
    	s[i]=0;
    	cin>>a>>b;
    	for(int j=1;j<=a;j++){
    		s[i]+=(pow(j,b));
		}
	}
	for(int i=0;i<n;i++){
		cout<<s[i]%10000<<endl;
	}
    return 0;
}