N Factorial!

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.

Sample

Input	Output
4 1 2 3 7	0001 0002 0006 5040