Факторіалом цілого числа \textbf{n} (позначається \textbf{n!}) називається добуток всіх цілих чисел від \textbf{1} до \textbf{n} включно. Факторіали швидко ростуть: \textbf{13!} вже не можна запам'ятати у \textbf{32}-бітовому цілочисельному типі більшості комп'ютерів, а \textbf{70!} вже велике для запам'ятовування у змінних дійсного типу. Ваша задача полягає у знаходженні правої ненульової цифри \textbf{n!}. Наприклад, \textbf{5!} = \textbf{1} * \textbf{2} * \textbf{3} * \textbf{4} * \textbf{5} = \textbf{120}, тому шуканою цифрою для \textbf{5!} є \textbf{2}. Також, \textbf{7!} = \textbf{1} * \textbf{2} * \textbf{3} * \textbf{4} * \textbf{5} * \textbf{6} * \textbf{7} = \textbf{5040}, тому відповіддю для \textbf{7!} буде \textbf{4}. \InputFile Перший рядок містить кількість тестів \textbf{T} (\textbf{T} < \textbf{15}). Кожен рядок є окремим тестом і містить ціле число \textbf{n}, між \textbf{1} і \textbf{1000} включно. \OutputFile Для кожного тесту вивести саму праву ненульову цифру \textbf{n!}