多少个1?

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

9 17

输出样例 #1

3

说明

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