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
prasoonbatham: 2017-01-20 15:26:54

Great question on bfs :)

chinmay0906: 2017-01-07 14:43:53

best question on bfs ^_^

ankushbbbr: 2017-01-04 21:15:17

nice question!! beware of-
1. long long overflow...use strings
2. try testcase 999,9999
3. modular arithmetic

tni_mdixit: 2016-10-25 14:39:02

really ,cool logic! though i couldn't crack :P

Last edit: 2016-10-25 14:39:24
piyush9620: 2016-10-16 18:16:41

instead of using bfs, we can use a counter. counter is basically a number counter.
but when u notice carefully, 1 -> 1, 2 -> 10, 3 -> 11, 4 -> 100 .... the binary representation of the counter value converted into equivalent decimal value can help us solve the problem. eg when value of counter is 5 -> 101 in binary, the number which we want would be 101 in decimal.

rohitranjan017: 2016-09-03 16:51:31

BFS + Backtracking !
AC ! :)

Sarthak Munshi: 2016-09-02 17:55:18

storing string or integer is trivial . Just store the remainder of leftchild%n and rightchild%n and check each of those to be 0 .

sonupmandal: 2016-08-19 12:39:17

backtracking :)

Last edit: 2016-08-19 12:56:01
vaibhavi760: 2016-08-14 12:39:19

weak test cases
try 999.

malibarbar: 2016-08-12 19:26:40

Got AC in one, 0,98
Check modular arithmetic
https://brilliant.org/wiki/modular-arithmetic/


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