Remote Training on Programming

(то же, что и задача 15, но с ограничением по памяти)

Факториалом натурального числа N (обозначается как N!) называется произведение всех натуральных чисел от 1 до N. Например, 5! = 1*2*3*4*5 = 120. Требуется написать программу, позволяющую для заданного N находить последнюю отличную от нуля цифру в числе N!

Input

В первой строке записано натуральное K<=1000. В каждой из следующих K строк записано очередное число N_i, для которого нужно получить ответ (1<=N_i<=1000000).

Output

Выведите K цифр, каждую в отдельной строке.

Sample