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: 2015-10-23 12:26:39

Used strings and queue and got accepted. But time taken was 4.02 seconds.

Advitiya: 2015-10-20 17:30:14

0.10s AC bfs +backtracking :'D

kartikay singh: 2015-10-20 13:48:34

bfs + backtracking -> AC :D
Wonder,how ppl did it in 0.00s??

Suhas Bhatt: 2015-10-11 09:47:58

Unsigned long long is not sufficient.... got two WA because of that :( string will do.

admiraldoge: 2015-09-15 20:23:02

Accepted in 1 go....................................... after a week of thinking this, even in the bed :/

[Mayank Pratap]: 2015-09-01 14:42:52

Pushing strings.... 7.2 s
Backtracking 0.1 s....

Last edit: 2015-09-01 17:21:27
rini22: 2015-08-19 13:53:50

weak test cases

nehaa: 2015-07-26 12:07:35

can someone help...how to solve this problem..
even if i use BFS and store numbers as string, then how to get number from large strings greater than 64 bits and check if it is fully divisible by given integer, or there is some other way to this.

Last edit: 2015-07-26 12:07:56
Mayank Ladia: 2015-06-23 00:48:13

Literally very weak test case....
I have printed "Pokemon" when n==1,
then too its accepting :p ....

Last edit: 2015-06-23 00:52:06
Shubham: 2015-06-11 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: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