给定 k 组数据，每组一个长度不超过 200 位的正整数 n，求 2011^n 的后四位（不足四位时直接输出模 10000 的结果，去掉高位多余的 0）。

输入格式

第一行为 k；之后 k 行，每行一个正整数 n。

输出格式

每行一个整数，即 2011^n 的后四位。

输入样例

2
1
2

输出样例

2011
4121

限制

时间限制：1000，内存限制：131072