Project Euler #26: Reciprocal cycles

_{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