题目描述

lhs 最近学习了网络知识，课后他搭建了两个网络圈，分别有 $a$ 个节点和 $b$ 个节点，并编号为 $0$ ~ $a-1$ 和 $0$ ~ $b-1$ 。

他在圈 $a$ 的一号节点放置了一条信息，同时也在圈 $b$ 的一号节点放置了一条信息。

在圈 $a$ 中，每过一秒，信息就会从 $i$ 号节点沿着网络链路转移到 $i+1$ 号节点，如果当前信息处于 $a-1$ 号节点，那么下一秒它会转移到 $0$ 号节点

在圈 $b$ 中也是类似的情况，不同的是如果信息处于 $b-1$ 号节点，那么下一秒会转移到 $0$ 号节点。

但是 lhs 一不小心搞错了参数，把每秒转移一次设置成了每 $0.000000001$ 秒转移一次

于是他根本看不清信息转移了几次，只注意到这两条信息在每个圈上都至少走了一圈，并且停下来时都处于 $k$ 号节点

现在他想知道信息至少被转移了多少次，你能帮他算算吗？

输入格式

一行三个正整数表示圈 $a$ 的大小，圈 $b$ 的大小，和 $k$ 。

输出格式

一个正整数表示答案 。

数据范围

对于 $30\%$ 的数据, $a,b\le 3000$

对于另外 $30\%$ 的数据, $a,b$ 互质

对于 $100\%$ 的数据， $a,b\le 10^9,k < \min(a,b)$

样例输入

4 5 1

样例输出

21