This problem is a programming version of Problem 26 from projecteuler.net
A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
Where means , and has a 1-digit recurring cycle. It can be seen that has a 6-digit recurring cycle.
Find the value of smallest for which contains the longest recurring cycle in its decimal fraction part.
Input Format
The first line contains an integer , i.e., number of test cases.
Next lines will contain an integer .
Constraints
Output Format
Print the values corresponding to each test case.
Sample Input
2
5
10
Sample Output
3
7