题目背景

试验场的密码锁每天换一次口令。管理员只记得卡片上的两个数字：底数 $a$ 和模数 $m$。锁里的寄存器每按一次按钮就做一次「乘 $a$ 再对 $m$ 取余」，一旦寄存器回到 $1$，整台锁就会自动重置。管理员想知道，自己最多要按多少次按钮才会看到重置。

题目描述

给定两个正整数 $a$ 与 $m$，满足 $a < m$。请求出最小的正整数 $t$，使得

如果不存在这样的正整数 $t$，请输出 -1。

输入格式

一行两个整数 $a, m$。

输出格式

一行一个整数，表示最小的 $t$，或者 -1。

输入输出样例 #1

输入 #1

3 7

输出 #1

6

输入输出样例 #2

输入 #2

2 9

输出 #2

6

输入输出样例 #3

输入 #3

6 9

输出 #3

-1

输入输出样例 #4

输入 #4

1 5

输出 #4

1

说明

样例解释

样例 1 中，$3,9,27,81,243$ 除以 $7$ 的余数依次是 $3,2,6,4,5$，都不到 $1$；$3^6 = 729 = 104 \times 7 + 1$，所以最小的 $t$ 是 $6$。

样例 2 中，$2$ 的幂除以 $9$ 的余数依次为 $2,4,8,7,5,1$，第六次回到 $1$，因此 $t = 6$。

样例 3 中，$6$ 与 $9$ 的最大公约数是 $3$，凡是 $6$ 的幂都能被 $3$ 整除，不可能除以 $9$ 余 $1$，所以输出 -1。

样例 4 中 $a = 1$，第一次乘完寄存器就已经是 $1$，$t = 1$。

数据范围

• 对于 $25\%$ 的数据，$m \le 400$；
• 对于 $60\%$ 的数据，$m \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le a < m \le 10^{12}$。