# 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 ≤ 10^{18}).

### 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

Input | Output |
---|---|

4 1 2 3 7 | 0001 0002 0006 5040 |

Login to submit