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
wttc: 2023-01-20 09:18:35

go to Errichto youtube channel, he's explained in depth.

khoaph: 2022-06-01 10:32:00

@aryan__0406
If n = 8, the result will be 1000

yasser1110: 2021-08-11 13:57:28

The question is good but I/O bounds should have been mentioned more clearly. Since the questioner has not bothered to provide that information let me provide it to you.

Input
1 <= n <= 20000

Output
may not fit in long long int

yzs: 2020-10-11 09:18:22

simple bfs to consider all possible permutations of 0 and 1, starting with 1. :)

knight_27: 2020-06-27 01:56:52

it is beautiful to understand a proof that an answer always exists

nandadeep_2001: 2020-06-12 13:16:16

can anyone explain the algorithm

cpp219: 2020-05-30 16:06:17

ez from LMH

aryan__0406: 2020-05-07 23:48:13

Good Question. Worth it!

aryan__0406: 2020-05-06 20:47:27

Every number till 20000 don't have such property such as 8.So in test cases only those numbers will be given which are valid.So chill!

cheesy: 2020-04-28 15:28:44

Is it guaranteed that an answer will exist?


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 PERL6 VB.NET
Resource:II Polish Olympiad in Informatics, Ist Stage