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
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?

ajaygupta007: 2020-04-08 10:31:07

1.learn how to compute mod of a big number using string.
2.use bfs

abhinav_jain02: 2020-03-11 08:33:21

A really good question to attempt.
Extremely good concept to keep a track of the mod values.

fran_1024: 2019-11-17 21:46:57

You don't need long division, you can simply mod the whole time with the number in input and remember the actual number only as a string and when the modded number becomes zero you return the string.


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