说明

青蛙小 C 听说 NOIP 要办周年庆比赛，兴冲冲得来到了 Z 市，初始时他在坐标 $x_0$ 处，小 C 是一只善于跳跃的青蛙，若当前他处在坐标 $x$ 处，每一次跳跃，他可以跳到 $4x+3$ 或 $8x+7$ 处，且由于体力原因，他最多能跳 $100000$ 次。

根据 Z 市的传说，坐标位置为 $10^9+7$ 的整数倍的位置（如 $10^9+7,2\times 10^9+14$）可以传送到 YZOJ。

小 C 想知道，最少跳几次能传送到 YZOJ。

输入格式

输入的第一行包含一个整数 $x_0$ 表示青蛙的初始位置，保证 $x_0$ 在的范围在 $[1,10^9+6]$。

输出格式

输出一个整数，表示最少所需步数，若在 $100000$ 步内还无法传送到 YZOJ，则输出 $-1$。

125000000 

1