说明

已知长度最大为200位的正整数$n$，请求出$2011^n$的后四位。

输入格式

第一行为一个正整数$k$，代表有$k$组数据，接下来的$k$行，每行都有一个正整数$n$。

输出格式

每一个$n$的结果为一个整数占一行，若不足4位，去除高位多余的0。

样例

3
5
28
792

1051
81
5521

数据范围

• $k≤200$
• $n的位数≤200$