Time Limit: 1000 mSec Memory Limit : 32768 KB

A classic string hashing algorithm can be simply described by the following code:

unsigned long long hash(string str)
{
unsigned long long ret= 5381;
int i;
for (i=0;i < str.size();i++)
ret=(ret* 33)^str[i]; //xor operation
return ret;
}

You will be given a hash value,and you shall determine that whether there exists a string with this hash value.

Note that the string you searching for must satisfy the following two conditions:

1.The length of the string is not large than 8.

2.The string is composed of characters whose ASCII code are between [0,128) .

Input contains multiple cases.Test cases are separated by several blank lines.

Each test case starts with a integer N(0 <= N < 2^64),which reperesents the hash value.

There are no more than 1000 test cases.

For each case,if there exists some satisfied string as described above,ouput the shortest length of such string,or just output -1 if we can’t find one.

193411340
210623374112
193415041
193434013
193422026

3
5
3
3
3