给定一个整数 $m$ 和一个整数序列 $z_1, \dots, z_n$。
对于每个 $z_i$，计算满足以下条件的整数对 $x, y$ ($0 \le x, y < m$) 的数量： $$x^2 + y^2 \equiv z_i \pmod m$$
输入格式
第一行包含两个整数 $m$ ($1 \le m \le 10^9$) 和 $n$ ($1 \le n \le 10^5$)。
第二行包含 $n$ 个整数 $z_i$ ($0 \le z_i < m$)。
输出格式
对于每个 $z_i$，输出满足 $x^2 + y^2 \equiv z_i \pmod m$ 的整数对 $x, y$ ($0 \le x, y < m$) 的数量。
样例
样例输入 1
3 3 0 1 2
样例输出 1
1 4 4
样例输入 2
4 4 0 1 2 3
样例输出 2
4 8 4 0
样例输入 3
5 1 3
样例输出 3
4