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
Shubham Garg:
20151023 12:26:39
Used strings and queue and got accepted. But time taken was 4.02 seconds. 

Advitiya:
20151020 17:30:14
0.10s AC bfs +backtracking :'D 

kartikay singh:
20151020 13:48:34
bfs + backtracking > AC :D


Suhas Bhatt:
20151011 09:47:58
Unsigned long long is not sufficient.... got two WA because of that :( string will do. 

admiraldoge:
20150915 20:23:02
Accepted in 1 go....................................... after a week of thinking this, even in the bed :/ 

[Mayank Pratap]:
20150901 14:42:52
Pushing strings.... 7.2 s


rini22:
20150819 13:53:50
weak test cases 

nehaa:
20150726 12:07:35
can someone help...how to solve this problem..


Mayank Ladia:
20150623 00:48:13
Literally very weak test case....


Shubham:
20150611 15:34:08
learnt a lot....had to take some help..for the record long long will pass easily..test case r weak....dont use string ...:D 
Added by:  PaweÅ‚ Dobrzycki 
Date:  20050526 
Time limit:  8s 
Source limit:  4096B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: NODEJS PERL 6 VB.net 
Resource:  II Polish Olympiad in Informatics, Ist Stage 