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
strings: 2012-12-19 10:39:38

@thefourtheye you didn't get my point. ! can precompute the values no doubt about that... but for those whose values lie outside long long?? 396,594,999,9999 etc are just xamples of some of those values... please tell what to do... strings?? precomputation??

thefourtheye: 2012-12-16 12:57:36

@C****** 396 => 11111111111111111100

strings: 2012-12-09 19:57:36

there are 235 test cases like 396,999,9999 etc which have reqd ans outside the limits of long long, so how to deal wid them??
strings?? precomputation??
please reply !!

rishabh jain: 2012-07-16 07:32:10

can anyone plz tell me d o/p for 999...i think it exceeds d range of long long..:(

Aman Kumar: 2012-02-12 18:52:55

thanx Marwan.....same thing happened wid me...:)

Crazzyy: 2011-11-20 05:50:53

very nice problem...enjoyed doing it :)

Anand Mohan Tiwari: 2011-11-09 16:34:30

clock nudging neurons

Anand Mohan Tiwari: 2011-11-09 16:22:44

cool

Marwan : 2011-03-19 14:16:04

using string my code got TLE (>8sec)
using long long with bitwise operations i got Ac at 1.29 sec
using int i got Ac at 1.09 sec :D :D

Last edit: 2011-03-19 14:16:36
Atulv: 2011-01-06 14:33:18

time limit is to strict so don't use strings.


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