Factorial

$n!$ denotes the factorial of an integer $n$, the product of all integers from $1$ to $n$. Factorials grow extremely quickly: $13!$ exceeds the range of a 32-bit integer on most computers, and $70!$ exceeds the range of most floating-point variables. We want to find the rightmost non-zero digit of $n!$. For example, $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$, so the rightmost non-zero digit of $5!$ is $2$. Likewise, $7! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 = 5040$, so the rightmost non-zero digit of $7!$ is $4$.

The first line contains the number of test cases $t$ ($0 < t < 15$). Each of the following $t$ lines contains a single integer $n$ ($0 < n < 1001$).

For each test case, print the rightmost non-zero digit of $n!$ on its own line.