The factorial of an integer \textbf{n}, written \textbf{n!}, is the product of all the integers from \textbf{1} through \textbf{n} inclusive. The factorial quickly becomes very large: \textbf{13!} is too large to store in a \textbf{32}-bit integer on most computers, and \textbf{70!} is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of \textbf{n!}. For example, \textbf{5!} = \textbf{1} * \textbf{2} * \textbf{3} * \textbf{4} * \textbf{5} = \textbf{120}, so the rightmost non-zero digit of \textbf{5}! is \textbf{2}. Also, 7! = \textbf{1} * \textbf{2} * \textbf{3} * \textbf{4} * \textbf{5} * \textbf{6} * \textbf{7} = \textbf{5040}, so the rightmost non-zero digit of \textbf{7!} is \textbf{4}. \InputFile The first line of the input contains the number of test case \textbf{T} (\textbf{T} < \textbf{15}). The single line which represents each test case contains an integer \textbf{n}, between \textbf{1} and \textbf{1000} inclusive. \OutputFile Print to the output the rightmost non-zero digit of \textbf{n!}