Факториалом целого числа \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!}