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

nikhil_sarda: 2019-11-13 08:00:36

c++ users..go for boost library

hetp111: 2019-08-25 09:51:10

Make sure to push s0 before s1, since s0<s1...

cegprakash: 2019-05-14 21:37:57

can also be solved using a famous 2 letter algorithm xD

Last edit: 2019-05-14 21:38:22
aditya_305: 2019-05-06 13:11:01

My code was not working for test case 99 and 999. I wasted around 1 hour thinking of some optimization. But later came to know that the test cases are very weak. very disappointed

letuantam96: 2019-03-20 09:08:01

Great problem. A lot of optimizion you have to do. Got it in 0.22s.

ab_biswas09: 2019-01-21 15:01:48

Nice problem , BFS + MODULAR ARITHMATIC =AC

Last edit: 2019-01-21 15:02:03
jmr99: 2018-10-16 11:07:39

wow just wow !! *__*

rajhim2: 2018-07-22 14:15:05

If one is using C++ then for numbers like n=19999,19953, etc. the multiples will exceed the limit of int and eventually you will have to use string. You will have to create a separate function for longDivision. If one is using python then it is very easy problem for python users.
For C++ users the approach is like this:
1. Code to generate binary numbers -- this is simple bfs problem.
2. Perform long division.

Last edit: 2018-07-22 14:15:45
oneinchatatime: 2018-06-03 19:19:57

Great problem!!
Weak test cases though :(


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