10855: 再倒水

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 结束。

1 <= a, b, c < 1000

Output

对于每组数据:若有解则输出最少被浪费的水量;若无解则输出 No solution!

Sample Input Copy

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

Sample Output Copy

10
0
176
No solution!

HINT

下面给出前 3 组样例的可行倒水步骤:

(0, 0) -> (7, 0) -> (0, 7) -> (7, 7) -> (4, 10) -(10 water wasted)-> (4, 0)

(0, 0) -> (0, 1) -> (1, 0) -> (1, 1) -> (2, 0) -> (2, 1) -> (3, 0)

(0, 0) -> (0, 9) -> (9, 0) -> (9, 9) -> (18, 0) -> (18, 9) -> (27, 0) -> (27, 9)
-> (36, 0) -> (36, 9) -> (44, 1) -(44 water wasted)-> (0, 1) -> (1, 0) -> (1, 9)
-> (10, 0) -> (10, 9) -> (19, 0) -> (19, 9) -> (28, 0) -> (28, 9) -> (37, 0)
-> (37, 9) -> (44, 2) -(44 water wasted)-> (0, 2) -> (2, 0) -> (2, 9) -> (11, 0)
-> (11, 9) -> (20, 0) -> (20, 9) -> (29, 0) -> (29, 9) -> (38, 0) -> (38, 9)
-> (44, 3) -(44 water wasted)-> (0, 3) -> (3, 0) -> (3, 9) -> (12, 0) -> (12, 9)
-> (21, 0) -> (21, 9) -> (30, 0) -> (30, 9) -> (39, 0) -> (39, 9) -> (44, 4)
-(44 water wasted)-> (0, 4)