题目：http://noi.openjudge.cn/ch0204/2991/

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char cb[205];
int b[205],c[205];
void input(){
	cin>>cb;
	b[0]=strlen(cb);
	for(int i=1;i<=b[0];i++)
		b[i]=cb[b[0]-i]-'0';
}
void gaoji(int b[],int t){
	memset(c,0,sizeof(c));
	c[0]=b[0];
	int jw=0;
	for(int i=b[0];i>=1;i--){
		c[i]=jw*10+b[i];
		jw=c[i]%2;
		c[i]=c[i]/t;	
	}
	while(c[c[0]]==0 && c[0]>1)c[0]--;
	for(int i=c[0];i>=0;i--)b[i]=c[i];
}
void quick_pow(int a,int b[],int c){
	int ans=1;
	while( (b[0]==1 && b[1]>0) || b[0]>1 ){
		if(b[1]%2==1) ans=ans*a%c;
		gaoji(b,2);
		a=(a*a)%c;
	}
	cout<<ans<<endl;
}
int main(){
	int a=2011,c=10000,T;
	cin>>T;
	while(T--){
		input();
		quick_pow(a,b,c);
	}
	return 0;
}