描述

桌上有两个水壶，容量分别为 $A$ 升和 $B$ 升（$1 \le A, B \le 100$）。一开始两个水壶都是空的（$(0, 0)$）。

每次你可以选择下面 6 种操作之一：

1. 把水壶 A 装满；
2. 把水壶 B 装满；
3. 把水壶 A 倒空；
4. 把水壶 B 倒空；
5. 把水壶 A 里的水倒进水壶 B，直到 A 空或 B 满；
6. 把水壶 B 里的水倒进水壶 A，直到 B 空或 A 满。

请你求出最少经过多少次操作，可以使任意一个水壶的水量恰好等于目标值 $T$（$0 \le T \le \max(A, B)$）。

如果无解，输出 -1。

输入格式

输入共一行，包含三个用空格隔开的整数 $A$, $B$, $T$。

输出格式

输出一行一个整数，表示最少操作次数。如果目标值不可能达到，输出 -1。

样例

样例输入 1

1 2 0

样例输出 1

0

解释：起始状态已经是 $(0, 0)$，水壶 A 的水量为 $0$，已满足目标 $T=0$，无需任何操作。

样例输入 2

3 5 4

样例输出 2

6

解释：经典 6 步方案（以 BFS 求出的最短序列为例）：

1. 装满 B：$(0, 5)$
2. B 倒入 A：$(3, 2)$
3. 倒空 A：$(0, 2)$
4. B 倒入 A：$(2, 0)$
5. 装满 B：$(2, 5)$
6. B 倒入 A：$(3, 4)$ ✓

样例输入 3

4 7 3

样例输出 3

2

解释：

1. 装满 B：$(0, 7)$
2. B 倒入 A：$(4, 3)$ ✓