Sphere Online Judge

SPOJ Problem Set (classical)

370. Ones and zeros

Problem code: ONEZERO


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
Resource:II Polish Olympiad in Informatics, Ist Stage

hide comments
2014-10-24 17:26:56 Yash Kumar
I think others are misleading, can easily be solved using stl and strings
2014-07-25 14:03:15 Dario Sindičić
190th :-D
2014-06-20 18:50:46 Master_Mind
getting wa.
any specific reasons plzz reply
2014-06-17 09:03:36 Archit Jain
dont use stl...!!


Last edit: 2014-06-17 09:26:47
2014-05-21 12:20:33 candide
@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
2014-05-21 07:45:51 Anubhav Bindlish
Will the answer fit in 64 bit integer?
2014-03-10 17:38:27 californiagurl
modular maths FTW :D (y) !!!!
hint: only one character array required
2014-01-21 18:38:58 Somesh Maurya™
ans for 19998??
2013-12-27 10:33:31 Srijan Khare
i think 9999 is not included in the test cases... anyway nice problem :)
2013-12-25 15:12:23 Gitanshu Behal
Finally Green Light :) Map and std:queues costed me 10+ TLEs....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.