Факториалы

Факториалом целого числа n (обозначается n!) называется произведение всех целых чисел от 1 до n включительно. Факториалы быстро растут: 13! уже нельзя запомнить в 32-битовом целочисленном типе большинства компьютеров, а 70! уже велико для запоминания в переменных действительного типа. Ваша задача состоит в нахождении правой ненулевой цифры n!. Например, 5! = 1 * 2 * 3 * 4 * 5 = 120, поэтому искомой цифрой для 5! является 2. Также, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, поэтому ответом для 7! будет 4.

Входные данные

Первая строка содержит количество тестов T (T < 15). Каждая строка является отдельным тестом и содержит целое число n, между 1 и 1000 включительно.

Выходные данные

Для каждого теста вывести самую правую ненулевую цифру n!

Примеры