Description

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:
1
= 0.5
= 0.(3)
= 0.25
= 0.2
= 0.1(6)
= 0.(142857)
= 0.125
= 0.(1)
= 0.1
10
Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1 has a 6-digit recurring cycle.
7
Find the value of smallest d < N for which 1 contains the longest recurring cycle in its decimal fraction part.
d
Input Format
The first line contains an integer T , i.e., number of test cases.
Next T lines will contain an integer N.
Output Format
Print the values corresponding to each test case.
Constraints
1 ≤ T ≤ 1000 4 ≤ N ≤ 10000
Sample Input

Sample Output