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
samanwaya: 2017-07-04 10:21:31

just wondering how broad is breadth first search.....!!!!

babur: 2017-06-27 07:02:14

Weak Test Cases....

himmi97: 2017-06-07 11:10:13

weak test cases..try 999 and 9999.
For 999 answer is 111111111111111111111111111

Last edit: 2017-06-07 11:11:41
codervrinda: 2017-05-25 13:30:33

@vipul_8 check for larger numbers...
check your code for test case:
1
999

vipul_8: 2017-05-25 11:13:15

can someone help.. why i'm getting wrong answer for this code http://ideone.com/U0MLF8

candide: 2017-05-01 10:13:44

Can also be solved with dynamic programming, but it's slow, about 0.16s.

Last edit: 2017-05-01 22:05:28
sucide: 2017-04-04 00:43:28

Ac in one go :)
Just draw tree to visualize
1
/ \
10 11
and do this using bfs then rest is upon you.

rishi_07: 2017-03-28 23:57:12

Great question!

anup108: 2017-03-22 11:52:20

answer for 999?

yashrocks22: 2017-02-26 19:46:53

AC in a single go!!,use array representation to store the whole tree and backtrack using bfs..

Last edit: 2017-02-26 20:20:51

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