A30166.【分治】【入门】2011

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

第一行为一个正整数k，代表有k组数据（k≤200），接下来的k行，每行都有一个正整数n，n的位数≤18。

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

提示：对于任意长度的ab，a与b的最后n位数字不变，则ab的结果最后n位数字不变；

如1232*131325=161792400；1231232*1325=1631382400；112331232*1111325=124836506402400


答案最后4位都是2400； 


所以题目中所有的数字均截取最后4位进行计算即可；


需要使用分治算法，否则不得分；