This problem is a programming version of Problem 129 from projecteuler.net
A number consisting entirely of ones is called a repunit. We shall define to be a repunit of length ; for example, .
Given that is a positive integer and , it can be shown that there always exists a value, , for which is divisible by , and let be the least such value of ; for example, and .
The least value of for which first exceeds ten is .
Given , compute .
Input Format
The first line of input contains , the number of test cases.
Each test case consists of a single line containing single integer, .
Constraints
Test files #1-2:
Test files #3-6:
Output Format
For each test case, output a single line containing a single integer, .
Sample Input
2
7
41
Sample Output
6
5
Explanation
As mentioned in the problem statement, and .