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

a_thinker: 2016-07-14 13:26:43

@candide how would that make a difference if we do bfs ending with the left most digits or bfs ending with the right most digits ?

invincible_rm: 2016-07-05 19:41:32

Used the Queue n the Modulo(n states) n Backtracked for number
AWESOME

Last edit: 2016-07-05 19:44:07
ajay_5097: 2016-05-26 17:13:42

easy one !! 2nd on bfs ! :)


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