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). Each of the next k lines contains a positive integer n, where the number of digits in n does not exceed 200.

Output Format

For each n, output the result as an integer on a separate line. If the result has fewer than 4 digits, remove any leading zeros.

## Example

### Input:
2
1
2

### Output:
2011
4121

### Explanation:
- For n=1, 2011^1 = 2011, so the last four digits are 2011.
- For n=2, 2011^2 = 4044121, so the last four digits are 4121.

3
5
28
792

1051
81
5521