时间限制：1秒　　内存限制：256M

---

【问题描述】

　　题目很简单：\(2019^n\) 的最后六位数字是多少？

【输入格式】

　　第一行为一个正整数 \(m\)，代表有 \(m\) 组数据；
　　接下来的 \(m\) 行，每行都有一个正整数 \(n\)，表示一组数据。

【输出格式】

　　每一组数数据的 \(n\)，输出一行一个整数，表示\(2019^n\)的最后六位数字，若不足 6 位，去除高位多余的 0。

【输入输出样例】

　Input

5
0
1
2
108
2019

　Output

1
2019
76361
685041
321979

【数据限制】

　　\(20\%\) 的数据满足，\(n≤10^4\)
　　\(50\%\) 的数据满足，\(n≤10^{18}\)
　　\(100\%\) 的数据满足，\(0<T≤100，0≤n≤10^{1000}\)

【来源】

　　Mr.he