题目描述

给定整数 $K$ 和质数 $m$，求最小的正整数 $N$，使得 $11\cdots1$（$N$ 个 $1$）$\equiv K \pmod m$。保证有解。

说人话：就是 $111\cdots 1111 \bmod m = K$。

输入格式

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

输出格式

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

9 17

3

提示

$30\%$ 的数据保证 $m\leq 10^6$。

$60\%$ 的数据保证 $m\leq 5\times 10^7$。

$100\%$ 的数据保证 $6\leq m\leq 10^{11}$，$0< K< m$，保证 $m$ 是质数。