该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

最近徐老师在学习《哈希》相关的知识，学到了一个概念叫——哈希冲突

也就是说对于一种哈希方式，如果两个不同的数字哈希出了同一个结果，那么就无法判别这两个数字，那么就意味着哈希出现了冲突

例如我们用 $x\%5$ 作为哈希规则，那么显然 $x=3$ 和 $x=8$ 时的哈希结果都是 $3$，那么我们就无法分别哈希结果 $3$ 到底代表 $3$ 还是 $8$，这就是哈希冲突

但是单纯这样的判断对徐老师来说太无聊了，于是徐老师想计算一下下列情况中有多少可能性会产生冲突

1. 选择两个正整数 $x,y$，满足 $x \leq y \leq n$
2. 哈希所使用的公式为 $id = (x^2+y^2) \% M$

徐老师想知道在确定 $M$ 的情况下，有多少可能性会出现哈希冲突

但是这个问题太复杂了，于是徐老师只询问你哈希值为 $0$ 的方案有多少种

输入格式

输入两个整数，分别为 $n,M$，含义如题

输出格式

输出一个整数，表示方案数

数据范围

对于所有数据满足 $n\le 10^9, M\le 10^6$

样例输入1

4 8

样例输出1

2

样例解释1

有以下 $2$ 种方案：

1. $x=2,y=2$
2. $x=4,y=4$

样例输入2

789 444

样例输出2

461