题目描述

​邻近端午节，有个叫ChasingZ的家伙特别喜欢吃粽子，这一次他想尝试自己去做，可惜他并没有足够的大米用来包粽子。但是，卖大米的DDD老板愿意给他提供 $x$ 粒大米，x需要满足以下两个条件：

1. $q(1\le q \le10^{18})$ 可以被$x$整除;
2. $x$不能被$p(1\le p \le10^9)$整除;

假设每个粽子需要$m(1\le m \le 10^5)$粒大米，ChasingZ想知道自己最多能吃多少个粽子（每个粽子必须是用m粒大米做的）。

虽然这是个easy的数学问题，但是对于只会吃的数学菜鸡ChasingZ来说，这实在是太难算了，所以他想请你帮他计算一下他最多能吃到多少个粽子。

输入格式

输入共一行，包含三个整数 $q(1\le q \le10^{18})$，$p(1\le p \le10^9)$ 和 $m (1\le m \le 10^5)$ 。

输出格式

输出一个数字$y$，表示ChasingZ最多能吃到多少个粽子。

样例

10 4 3

3

12 6 2

2