Description

Given a positive integer $n$ with a maximum length of $200$ digits, find the last four digits of $2011^n$.

Input Format

The first line contains a positive integer $k$, representing the number of test cases ($k ≤ 200$).
The next $k$ lines each contain a positive integer $n$, where $n$ has at most $200$ digits.

Output Format

For each $n$, output a single line containing the last four digits of $2011^n$. If the result has fewer than $4$ digits, remove any leading zeros.

Sample

3
5
28
792

1051
81
5521