题目描述

有两个无刻度标志的水壶 $A$ 水壶和 $B$ 水壶，其中 $A$ 水壶可装 $x$ 升水, $B$ 水壶可装 $y$ 升的水。

设另有一水缸(有无限水，也可以装无限水)，可用来往 $A$ 水壶或 $B$ 水壶灌满水或者倒出 $A$ 壶或者 $B$ 壶的水，两水壶间，水可以相互倾灌。

已知 $A$ 水壶开始时满壶，$B$ 水壶为空壶，问通过倒水或者灌水操作，最少用多少步才能在 $B$ 壶中量出 $z$ 升水来。

输入格式

输入一行共三个正整数 $x,y,z$

输出格式

输出一行为最少的步数，如果无法达到目标，则输出 No solution!。

8 5 3

3

样例 1 解释

第 $1$ 步: 将 $A$ 壶中水倒满 $B$ 壶, $A$ 剩余 $3$ 升, $B$ 剩余 $5$ 升

第 $2$ 步: 将 $B$ 壶中水全部倒出, $A$ 剩余 $3$ 升, $B$ 剩余 $0$ 升

第 $3$ 步: 将 $A$ 壶水全部倒入 $B$ 壶中, $A$ 剩余 $0$ 升, $B$ 剩余 $3$ 升

22 75 51

83

数据规模与约定

对于 $100\%$ 的数据，$x,y\le 100, z <= y$。