# 2831. Factorials

The factorial of an integer n, written n!, is the product of all the integers from 1 through n inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Also, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

### 输入格式

The first line of the input contains the number of test case (<15). The single line which represents each test case contains an integer n, between 1 and 1000 inclusive. . ..

### 输出格式

Print to the output the rightmost non-zero digit of n!

### 样例

Input
1
5

Output
2


47 人解决，60 人已尝试。

55 份提交通过，共有 139 份提交。

7.6 EMB 奖励。