/* OnesZeroes : Given a positive integer X, find the smallest positive
 *     integer Y such that X*Y = P is written in all 1's and 0's
 *     (in base 10), assuming such a Y exists.
 *     E.g., If X = 3, then Y = 37 works, as 3*37 = 111.
 *     Likewise, 1294717 * 850386687593583 = 1101010101001101001011.
 *
 * The general question had been
 *     forall X in Naturals - {0}. exists Y in Naturals - {0}.
 *         exists E subset Naturals. |E| in Naturals and
 *             PRODUCT(I in E) 10^I = X*Y ?
 * That is, for any positive integer X, does there have to exist another
 * positive integer Y such that X*Y is written in all 1's and 0's
 * in base 10?
 *
 * ALGORITHM
 *     Given X, explore each all-ones-and-zeroes number (a "ZO") P
 *     from smallest (starting with length same as X) ascending.
 *     So if X is 17, we explore 10, 11, 100, 101, 110, 111, 1000, ...
 *     We stop once we find a ZO P such that P mod X = 0.  Note that,
 *     if there is no such ZO, we explore forever!
 *
 * CONSIDERATIONS
 *     The smallest ZO that works for a given X may be very large,
 *     even larger than would fit in a LONG. So we should use some
 *     type of special math where this is not a problem.
 *
 * Parke Godfrey, 2009-9-15
*/

import java.io.PrintStream;
import java.math.BigInteger;

public class OnesZeroes
{
    public static void main(String[] args)
    {
        PrintStream output = System.out;

        BigInteger x; // The integer to test.
        long tries;   // How many numbers (P's) we tried before finding Y.

        // Process each integer from the command-line arguments.
        for (int a = 0; a < args.length; a++)
        {
            // Grab the next x from the command-line arguments.
            try
            {
                x = new BigInteger(args[a]);
            }
            catch (Exception e) {
                output.printf("\"%s\" is not an integer.\n", args[a]);
                continue;
            }
            // Check that our integer is positive.
            if (x.compareTo(BigInteger.ZERO) <= 0) {
                output.printf("\"%s\" is not a positive integer.\n", args[a]);
                continue;
            }

            // P is a "number" of just 1's and 0's.
            // We will walk through these from smallest up,
            // until we find a P such that P mod X is 0.
            // I.e., 1, 10, 11, 100, 101, 110, 111, ...
            // (Actually, we start with the smallest P the same
            // digit-length as X, to be a little more efficient.)
            String p = "1";
            for (int i = 0; i < x.toString().length() - 1; i++)
                p += "0";

            tries = 1;
            while (new BigInteger(p).mod(x).compareTo(BigInteger.ZERO) != 0)
            {
                // Construct the next p.
                // First, find rightmost zero in p.  -1 for none.
                int i;
                int pLen = p.length();
                for (i = pLen - 1; i >= 0 && p.charAt(i) != '0'; i--);
                // Replace that zero with one, and all to the right
                // with zeroes.  E.g., 10011 => 10100.
                if (i >= 0)
                {
                    p = p.substring(0, i);
                    p += "1";
                }
                // Otherwise, the string was all one's.  Make string
                // one place longer, commencing with a one, followed by
                // all zeroes.  E.g., 111 => 1000.
                else
                {
                    p = "1";
                }

                for (i++; i < pLen; i++) p += "0";
                tries++;
            }

            // Found a P that works!  (Note that Y = P / X.)  Report.
            output.print(x + " * ");
            output.print((new BigInteger(p)).divide(x)); // Y
            output.print(" = " + p);
            output.println(" (in " + tries + " tries)");
        }
    }
}