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
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.

Priyank: 2010-04-28 02:31:41

Test cases are weak.
Add "9999".

Last edit: 2011-11-19 14:28:59

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