URI Online Judge | 1705

Binary Lover

By ICMC-USP BR Brazil

Timelimit: 2

In order to improve her scientific skills Princess Bubblegum has learned to program using BMO (the best computer in the Candy Kingdom), and as any programmer she has become a binary lover.

By her addiction to binary stuff, she also loves any decimal number that looks like a binary number (i.e. a decimal number that only has digits 0 and 1, for example 101), so she was trying to find a multiple of a given decimal number N that looks like a binary number, but for some numbers it was taking a long time to find such multiple, even with the help of BMO. Due to the princess addiction to problem solving, she hasn’t been doing anything until she gets the desired multiples. That situation was perfect for the Earl of Lemongrab, who took over the Candy Kingdom. As Finn and Jake, the Candy Kingdom heroes, can’t do anything against the Earl of Lemongrab and don’t know nothing about multiples, they asked you to save the Candy Kingdom by finding the desired multiples.

Input

The input will consist of at most 2*10^5 lines, each line consist of an integer N (0 < N < 10^12) for which Princess Bubblegum wants to find the described multiple M(M != 0), this number must be less than 10^12, otherwise it wouldn’t fit in the BMO architecture.

Output

For each integer in the input print a line with the required multiple, if there exist several solutions print the smallest of them, if there is no solution print -1.

Sample Input Sample Output

143

1217

3123

1783

101

1001

101011

-1

1100111

101