Background

NOIP is about to celebrate its anniversary. Over this journey, NOIP has led OIers nationwide, building an efficient, stable, fast, and open socialist-modern OI. In the new year, YZOJ will continue to make progress, actively exploring paths for growth to better serve the broad community of OIers.

Problem Description

Little Frog C heard that NOIP will hold an anniversary contest and excitedly came to Z City. Initially, he is at coordinate $x_0$. Little Frog C is good at jumping: if he is currently at coordinate $x$, with each jump he can move to $4x+3$ or $8x+7$. Due to stamina limits, he can make at most $100000$ jumps.

According to the legend of Z City, any position whose coordinate is a multiple of $10^9+7$ (e.g., $10^9+7,2\times 10^9+14$) can teleport to YZOJ.

Little Frog C wants to know the minimum number of jumps needed to teleport to YZOJ.

Input Format

The first line contains an integer $x_0$, the frog’s initial position, guaranteed to be in the range $[1,10^9+6]$.

Output Format

Output a single integer, the minimum required number of steps. If he still cannot teleport to YZOJ within $100000$ steps, output $-1$.

125000000 

1

Hint

Translated by ChatGPT 5