Description

众所周知，N 的阶乘𝑁! = 1 × 2 × 3 … × 𝑁。阶乘的增长啪的一下就起来了，很快啊。所以在这道

题中只需要你求出 N!末尾第一个非零数是多少。例如 5!=120，则 5!末尾第一个非零数是 2。

Input

第一行包含一个整数 T 表示数据组数。

每组数据一行，包含一个正整数 N。

Output

共 T 行，每行输出 N!末尾的第一个非零数。

Samples

6 
1 
2 
26 
125 
3125 
9999

1 
2 
4 
8 
2 
8

Limitation

对于前 30%的数据，N<10000。

对 100%的数据，T≤ 6,N≤ 10500。