题目描述

给出正整数 $N$（可能有前导0），请求出 $N!$ 最右非零的数位的值。

输入格式

第一行一个数 $T$ 表示数据组数 $T<=10$

下接 $T$ 行,每行一个数 $N$ 表示一组数据N<=10^100

输出格式

对于每组数据，输出一行一个数表示这组数据的答案

样例输入

2
5
4

样例输出

2
4