AMOEBA - Amoeba

Dr. Fulano found a new species of microorganism, the fast-growing-amoeba. The colony of this kind of amoeba grows vary fast. To find out the exactly rate of growth of the colony, Dr. Fulano wrote down for several days, the number of amoebae in the colony. Soon he realized that each individual generate daily, 6 new individuals. As the number of amoebae grew very quickly, Dr. Fulano noted only the last K digits. When he realized that the numbers noted were repeated, it was too late! The research was already well advanced and there was no time to recount. The solution was to ask for help from you.

Dr. Fulano will give to you a number of K digits (0 < K < 10), possibly with leading zeroes. You should answer the first day he wrote down that number. Consider that in day 1, the colony was composed of 1 amoeba. Consider also that an amoeba does not disappear when generating his descendants.

If there is no answer to the number given, print -1.

Input

The input is composed by various numbers, each in one line.

Output

For each line in input, print a line in output. The line should contains the required answer without leading zeroes.

Example

Input:
01
143
743
600

Output:
1
20
12
-1

Added by:Paulo Costa
Date:2012-01-19
Time limit:0.301s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFPE

hide comments
2015-05-21 12:35:43 vivek keshore
I didn't understand the question perhaps. How the output is 20 for k=143 and 12 for k=743. Can someone explain the problem or the output?
2014-03-08 08:09:13 anurag garg
AC...finally
maximum ans is less than 10^6

Last edit: 2014-03-08 08:42:05
2014-02-23 15:17:05 Bhavik
what can be the maximum ans??

Last edit: 2014-02-23 15:19:09
2012-04-17 03:29:14 freaking guy!!!
uzumaki: Read until the eof..
2012-04-15 20:59:39 uzumaki_naruto
what is the no of input cases??
2012-04-09 01:27:07 Fernando Fonseca [ITA]
Diogo: I believe you're correct on both accounts.

Last edit: 2012-04-09 01:27:16
2012-04-09 00:04:14 Diogo Soares [UFAM]
each output line has just 1 answer for each input line?? Is it the minimum number possible of days?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.