题目描述

徐老师最近很喜欢玩《大富翁》。

在他玩的这款游戏里，有两种特殊的骰子——“指定骰子”和“倍数骰子”。

• 指定骰子：可以向前移动 $1\sim k$ 步，具体移动步数由玩家指定。
• 倍数骰子：假设当前位置为 $x$ 号点，可以直达 $x\times p$ 号点，其中 $p$ 是游戏中固定的一个数值。

玩家的任务是从 $1$ 号点出发，移动到 $E$ 号点结束。玩家必须恰好站在 $E$ 号点才能获胜，如果超过了则游戏失败。

现在徐老师想知道，如果可以无限使用这两种骰子，最少需要使用几次骰子可以获胜？

输入格式

本题采用文件读写。

• 读入文件名：dice.in
• 写出文件名：dice.out

第一行包含三个整数 $k,p,E$，含义如题。

输出格式

输出一个整数，表示最少的骰子使用次数。

样例

1 2 8

3

1 2 10

4

1 2 123

11

样例说明

样例 1 的一种方案为：$1\to2\to4\to8$。

样例 2 的一种方案为：$1\to2\to4\to5\to10$。

数据范围与提示

• 对于 $20\%$ 的数据，$E\le1000$。
• 对于 $40\%$ 的数据，$E\le10^5$。
• 对于另外 $20\%$ 的数据，$E\le10^{18}$，$k\le1000$，$p=1$。
• 对于 $100\%$ 的数据，$E\le10^{18}$，$k\le p\le1000$。