题目描述

考虑方程 $x^k + y^k = z^k$，其中 $x,y,z,k$ 均为正整数。众所周知，由费马大定理，当 $k>2$ 时方程无解。现在考虑在模意义下的问题。

给定一个质数 $P$，以及一个正整数 $L$，现在想知道有多少个整数 $k$，满足 $1 \le k \le L$，存在 $x,y,z$，$0 < x,y,z < P$，使得：

输入格式

输入两个整数 P, L。

输出格式

输出一个整数，代表合法的 k 的个数。

数据范围

• 对于 10% 的数据：P <= 100, L <= 100
• 对于 30% 的数据：P <= 5000, L <= 5000
• 对于 60% 的数据：P <= 1e6, L <= 1e5
• 对于 100% 的数据：P <= 1e6, L <= 1e18

输入样例

样例输入 1

3 10

样例输入 2

233 1000

样例输入 3

692707 470472961806427201

输出样例

样例输出 1

5

样例输出 2

966

样例输出 3

470453944730018769