C. Baklava Baking
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Janise is baking a honey baklava with $$$N$$$ layers. She knows that if she reverses $$$N$$$, she will get a number divisible by $$$5$$$. Janise wants to know how many possible baklavas with $$$9$$$-digit $$$N$$$ satisfy this property that have a layer count $$$N$$$ that is divisible by $$$K$$$. Can you help her calculate this?

Input

The first line contains $$$T$$$ ($$$1 \leq T \leq 10^5$$$), the number of test cases. The next $$$T$$$ lines each contain a single integer $$$K$$$ ($$$1 \leq K \leq 10^5$$$).

Output

For each of the $$$T$$$ test cases, output the total number of possible baklavas Janise could bake on a new line.

Example
Input
5
1
2
3
4
5
Output
100000000
50000000
33333333
25000000
20000000