# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## N Factorial!

Limits: 1s, 512 MB

I like short descriptions and I think you so too.

Let’s say you have a number, N. Now try to find the last four digits of N!.

Actually It’s too easy.

I think you know that $N! = (1 \times 2 \times 3 \times ... \times N)$.

### Input

The input begins with a single integer indicating the number of test cases T (1 ≤ T ≤ 100). Each of the following test cases consists of a number N (0 ≤ N ≤ 1018).

### Output

For each test case output the last four digits of N factorial (N!).

If N! is less than 4 digits don’t forget to add 0s to left.

### Samples

InputOutput
4
1
2
3
7
0001
0002
0006
5040

Discussion
Submit