Migrated from Lutece 3000 添数游戏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

塔菲在和东雪莲玩一个游戏。 塔菲给了东雪莲一个集合$S$和一个数$n$。初始集合中只有一个数$1$，每次操作东雪莲可以从集合中选择两个数$A$与$B$（$A$与$B$可以相等），然后将$A+B$加入集合或者将$|A-B|$加入集合。 请问东雪莲最少需要多少次操作才能使$n$在集合中？

Input

一个整数$n$

Output

一个整数，代表最少需要的操作次数

Samples

31

6

Constraints

$1 \leq n \leq 20000$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming