说明

关于兔子~蹦蹦跳跳的兔子~谨以此题膜拜Rabbit大神。

话说小兔兔跳得很远，如果他处于位置x，则他能跳到4x+3或8x+7的位置，但是由于环境不好，只有%1,000,000,007=0的位置才有草。

但是小兔兔很饿，他最多只能跳100,000次，问，他最少需要跳几次才能吃到草？

如果他吃不到草，输出-1。

假设小兔兔的位置是281250001，则他先跳到1125000007（4x+3），再跳到9000000063(8x+7)。9000000063=9*1000000007。所以需要跳两次。

输入格式

一个数x，表示小兔兔的位置，n<1,000,000,007

输出格式

一个数，最少跳的次数，如果在规定步数内吃不到草输出-1.

125000000
281250001

1
2