指定质因数出现几次

题目描述

给定整数 n 和质数 p，求 n 的标准质因数分解中 p 的指数，即最大的非负整数 e，使 p^e 能整除 n。

输入格式

一行输入 n、p，满足 2≤n≤10^12、2≤p≤10^9，并保证 p 为质数。

输出格式

输出指数 e；若 p 不能整除 n，输出 0。

样例

输入

360 2

输出

3