ONEZERO - Ones and zeros

no tags 

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

Added by:PaweĊ‚ Dobrzycki
Date:2005-05-26
Time limit:8s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource:II Polish Olympiad in Informatics, Ist Stage

hide comments
BRAIN: 2015-04-15 16:10:10

7.42s with C++ ( cin, cout ) :-ss . .......
algorithm using bfs and a binary tree with any node is 0 and 1

Rajat (1307086): 2015-04-05 13:05:23

Brilliant question. Just look at my history of submissions of this question:
first submission on 30/06/2014
AC on 05/04/2015

vijay : 2015-03-12 19:12:45

A Brilliant question . Guys jst do it urself. All the time will be worth.Dot

Stanley: 2015-01-18 22:56:32

I cant solve it... The only way i know is making a list with all numbers with ones and zeros... I only know C :(

Last edit: 2015-01-19 00:36:46
deepak garg: 2015-02-05 17:51:43

good one!

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

My 50th!!!!!!

Samar Holkar: 2015-01-17 18:40:04

Last edit: 2015-01-17 18:40:23
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