10854: 倒水

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

两个容量分别为 a 和 b 的容器,通过三种操作,直到某一容器装有体积为 c 的水,同时另一容器为空,使倒水次数最少。初始时容器皆空。三种操作分别为:把某容器全倒到下水道;把某容器用水龙头接满;从甲容器向乙容器倒水直到甲空或乙满。

Input

每组数据包含三个整数 abc。输入以 EOF 结束

Output

对于每组数据:若有解则输出最少的倒水次数;若无解则输出 No solution!

Sample Input Copy

7 10 4
58 1 3
44 9 4
3 8 10

Sample Output Copy

5
6
47
No solution!