팩토리얼

$n!$ 은 정수 $n$ 의 팩토리얼로, $1$ 부터 $n$ 까지 모든 정수의 곱을 의미한다. 팩토리얼은 매우 빠르게 커져서 $13!$ 은 대부분의 컴퓨터에서 32비트 정수의 범위를, $70!$ 은 대부분의 부동소수점 변수의 범위를 넘어선다. 우리는 $n!$ 에서 0이 아닌 가장 오른쪽 자리 숫자(the rightmost non-zero digit)를 찾으려고 한다. 예를 들어 $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$ 이므로 $5!$ 의 0이 아닌 가장 오른쪽 숫자는 $2$ 이다. 마찬가지로 $7! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 = 5040$ 이므로 $7!$ 의 0이 아닌 가장 오른쪽 숫자는 $4$ 이다.

첫 줄에 테스트 케이스의 수 $t$ ($0 < t < 15$)가 주어진다. 이어지는 $t$ 개의 줄에 각각 정수 $n$ 이 하나씩 주어진다 ($0 < n < 1001$).

각 테스트 케이스마다 $n!$ 의 0이 아닌 가장 오른쪽 자리 숫자를 한 줄에 하나씩 출력한다.