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
deepak garg: 2015-02-05 17:51:43

good one!

SHUBHAM PANDEY: 2015-01-17 18:47:03

My 50th!!!!!!

Dhawal Harkawat: 2015-01-03 09:51:54

for those getting WA.. ->
please note that unsigned long long int would not help here..

Nongthonbam Tonthoi: 2014-12-29 20:42:41

I will try later.

Last edit: 2014-12-29 20:47:09
1yr: 2014-12-25 21:26:14

no need of even string/vector

Yash Kumar: 2014-10-24 17:26:56

I think others are misleading, can easily be solved using stl and strings

Dario Sindicic: 2014-07-25 14:03:15

190th :-D

Master_Mind: 2014-06-20 18:50:46

getting wa.
any specific reasons plzz reply

Archit Jain: 2014-06-17 09:03:36

dont use stl...!!

Last edit: 2014-06-17 09:26:47
candide: 2014-05-21 12:20:33

@Anubhav Bindlish
even if you ignore data not coprime to 10, it remains a few cases (about one hundred) not fitting in a 64 bit integer


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