Факторіали

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

Приклади