# 题目描述
# 小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x_0。
# 对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 * x + 3或者8 * x + 7。因为使用
# 神秘力量要耗费太多体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007
# 整除的位置(比如：位置0，位置1,000,000,007，位置2,000,000,014等)。小易需要你帮忙计算最
# 少需要使用多少次神秘力量就能吃到贝壳。
# 输入描述:
# 输入一个初始位置x_0,范围在1到1,000,000,006
# 输出描述:
# 输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-1

def Solution(a):
    temp=[a,4*a+3,16*a+15]
    for j,m in enumerate(temp):
        for i in range(100000):
            m=(m*8+7)%1000000007
            if m==0:
                return i+j+1
    return -1
  
a=int(raw_input(""))
ans=Solution(a)
print ans

# 设f(x)=4x+3,g(x)=8x+7。
# 计算可以得到以下两个规律：
# （1）  g(f(x))=f(g(x))   即f和g的执行顺序没有影响。
# （2）  f(f(f(x)))=g(g(x))    即做3次f变换等价于做2次g变换
#     由于规律（1） 对于一个可行方案，我们可以调整其变换的顺序。如ffggfggff，我们可以转化成 fffffgggg。
#     由于规律（2），并且为了使执行次数最少，每3个f我们可以转化成2个g，如方案fffffgggg，可以转化成ffgggggg。
#     因此一个最优的策略，f的执行次数只能为0,1,2。对于输入的x，我们只需要求x，4x+3,4（4x+3）+3的最小g执行次数就可以了。