ONEZERO - Ones and zeros


Certain positive integers have their decimal representation consisting only of ones and zeros, and having at least one digit one, e.g. 101. If a positive integer does not have such a property, one can try to multiply it by some positive integer to find out whether the product has this property.

Input

Number K of test cases (K is approximately 1000);
in each of the next K lines there is one integer n (1 <= n <= 20000)

Output

For each test case, your program should compute the smallest multiple of the number n consisting only of digits 1 and 0 (beginning with 1).

Example

Input:
3
17
11011
17
Output:
11101
11011
11101

hide comments
coderkoko: 2016-01-23 14:46:57

Can anyone help e out? why getting WA? http://ideone.com/tPJJLK

minhthai: 2016-01-12 12:01:40

very nice problem. that example tests though :v
for java, you need to optimize a bit your bfs

karan: 2015-12-29 10:01:35

weak test cases. try for 999 and 9999.

kshitij tripathi: 2015-12-26 21:21:39

Nice Problem :)

vipul grover: 2015-12-10 10:44:24

finally after so many attempts :)

aghori_sadhu: 2015-12-07 05:16:44

BFS+states

Shubham Garg: 2015-10-23 12:26:39

Used strings and queue and got accepted. But time taken was 4.02 seconds.

Advitiya: 2015-10-20 17:30:14

0.10s AC bfs +backtracking :'D

kartikay singh: 2015-10-20 13:48:34

bfs + backtracking -> AC :D
Wonder,how ppl did it in 0.00s??

Suhas Bhatt: 2015-10-11 09:47:58

Unsigned long long is not sufficient.... got two WA because of that :( string will do.


Added by:PaweĊ‚ Dobrzycki
Date:2005-05-26
Time limit:8s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL 6 VB.net
Resource:II Polish Olympiad in Informatics, Ist Stage