Project Euler #129: Repunit divisibility

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