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.

Input

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

Output

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

Examples