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
magpie03: 2016-07-22 10:50:59

I don't know why I am getting wrong answer when my program is giving answer for 999-"111111111111111111111111111" and for 1998 -"1111111111111111111111111110". I am using bfs to find out the smallest number multiplying which with input the product turns to be all zero and then printing their product. Can anyone suggest something. I am doing in c

a_thinker: 2016-07-14 13:26:43

@candide how would that make a difference if we do bfs ending with the left most digits or bfs ending with the right most digits ?

surayans tiwari(http://bit.ly/1EPzcpv): 2016-07-10 06:31:33

for n=1 answer shud be 1 ,, but i got accepted with my answer being 10, weak test cases

invincible_rm: 2016-07-05 19:41:32

Used the Queue n the Modulo(n states) n Backtracked for number
AWESOME

Last edit: 2016-07-05 19:44:07
ajay_5097: 2016-05-26 17:13:42

easy one !! 2nd on bfs ! :)

candide: 2016-05-16 01:58:46

@kartikay singh: "Wonder,how ppl did it in 0.00s??"

Response: I did using a bfs ending with the left most digits of the number we are asked for. On the contrary, the most common and intuitive bfs method ends with the right most digit, and even optimised the later bfs needs 0.03s or more. Perphaps there exists a more mathematical (and ad hoc) method.

Last edit: 2016-05-25 17:14:50
zdratcha: 2016-04-28 21:35:28

bfs and backtracking got me an AC :)

coderkoko: 2016-01-23 14:46:57

Can anyone help e out? why getting WA? http://ideone.com/tPJJLK

minhthai: 2016-01-12 12:01:40

very nice problem. that example tests though :v
for java, you need to optimize a bit your bfs

karan: 2015-12-29 10:01:35

weak test cases. try for 999 and 9999.


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 PERL 6 VB.net
Resource:II Polish Olympiad in Informatics, Ist Stage