多少个 1?

题目描述

给定整数 $K$ 和质数 $m$,求最小的正整数 $N$,使得 $ 11\cdots1$($N$ 个 $1$)$\equiv K \pmod m$。 说人话:就是 $111\cdots 1111 \bmod m = K$。

输入输出格式

输入格式


第一行两个整数,分别表示 $K$ 和 $m$。

输出格式


一个整数,表示符合条件最小的 $N$。

输入输出样例

输入样例 #1

9 17

输出样例 #1

3

说明

$30\%$ 的数据保证 $m\leq 10^6$。 $60\%$ 的数据保证 $m\leq 5\times 10^7$。 $100\%$ 的数据保证 $6\leq m\leq 10^{11}$,$0< K< m$,保证 $m$ 是质数。