## 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
 codeking123: 2018-03-14 18:29:44 thanks to tarun tarun2619: 2018-02-24 05:46:21 For optimizing bfs : https://www.geeksforgeeks.org/find-the-smallest-binary-digit-multiple-of-given-number/ sagarstorm: 2018-01-22 15:40:35 Nice problem, lot of things to take care of yashgulani: 2017-11-07 21:20:34 test cases are weak , there is no test case having n=1 boundary condition . Please improve the test case for this particular question . aditya930: 2017-10-20 15:47:04 getting WA can someone help wrong answer code is https://ideone.com/SMd9dj vishesh197: 2017-10-17 17:11:10 did it using bfs ......but used modular arithmetic for checking remainder....it took me 5.44sec but AC in first go.Can anybody help me with my implementation.... nadstratosfer: 2017-10-17 10:37:54 If you come here to practice BFS, look elsewhere. It's basically a bruteforce trial division over binary-looking numbers. People raving about smart-sounding acronyms here remind me of binmen calling themselves "environmental officers". rohit1507: 2017-09-20 13:28:01 Fcking awesome!!! Question worth giving time! matcha1998: 2017-09-18 08:12:02 Excellent one!! samanwaya: 2017-07-04 10:21:31 just wondering how broad is breadth first search.....!!!!

 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