Tsinghua-HKUST Programming Contest 2007: Problem D

Problem D - Repetitive Multiple

An integer is said to be repetitive if it can be written as a concatenation of several copies (at least two) of another non-zero-leading integer. For example, 11, 123123, 454545 are all repetitive integers.

Since zero-leading integers are not allowed, 101 can not be considered as 0101. Therefore, 101 is not repetitive.

Given a positive integer n, what is the smallest repetitive integer which is a multiple of n.

Input
The input begins with an integer N (≤ 100) which indicates the number of test cases followed. Each of the following test cases consists of a positive integer n, where n will be less than 10⁹.

Output
For each test case, print out the smallest repetitive multiple of n in a single line.

Sample input

5
7
101
123
999999
6339673

Sample output

77
1010
33333
999999
114114114

Problem setter: Cho
Source: Tsinghua-HKUST Programming Contest 2007