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
Anubhav Bindlish: 2014-05-21 07:45:51

Will the answer fit in 64 bit integer?

californiagurl: 2014-03-10 17:38:27

modular maths FTW :D (y) !!!!
hint: only one character array required

Somesh Maurya™: 2014-01-21 18:38:58

ans for 19998??

Srijan Khare: 2013-12-27 10:33:31

i think 9999 is not included in the test cases... anyway nice problem :)

Gitu: 2013-12-25 15:12:23

Finally Green Light :) Map and std:queues costed me 10+ TLEs....

Akshat Jain: 2013-12-17 18:25:25

Nice problem....avoid string

Last edit: 2013-12-18 05:39:51
(^-^): 2013-12-15 16:36:38

very nice question!!

aar: 2013-10-25 12:50:34

Very good question.. BFS.. Must solve.. Solved in 9 hrs, but was worth...

_maverick: 2013-09-22 07:57:42

Have an optimized I/O and some tricks up sleeve to get AC ... btw dont need strings for and it keep it simple ... excellent problem , spent 6 hours on it and enjoyed .. XD.

aqfaridi: 2014-05-26 12:14:44

finally got AC...
vry nice prob!!


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