Аркадий и его друзья любят играть в шашки на доске \(n \times n\). Строки и столбцы доски пронумерованы от \(1\) до \(n\).
Друзья недавно выиграли какой-то турнир, поэтому Аркадий хочет поздравить их и подарить конфеты. Вспомнив старинную притчу (но не ее мораль), Аркадий решил дать друзьям по одному набору конфет за каждую клетку доски: набор конфет, соответствующий клетке \((i, j)\), будет состоять из ровно \((i^2 + j^2)\) конфет особенного для этой клетки типа.
Всего друзей, выигравших турнир, \(m\). Сколько же из этих \(n \times n\) наборов конфет можно разделить поровну на \(m\) частей, не разделяя конфеты на части? Обратите внимание, что каждый набор нужно делить независимо, так как конфеты в разных наборах разные.
Выходные данные
Выведите одно целое число — количество наборов, которые можно поделить поровну.
Примечание
В первом примере только набор, соответствующий клетке \((3, 3)\), может быть разделен поровну (\(3^2 + 3^2 = 18\), а это делится на \(m=3\)).
Во втором примере наборы, соответствующие следующим клеткам, могут быть разделены поровну:
- \((1, 2)\) и \((2, 1)\), поскольку \(1^2 + 2^2 = 5\), что делится на \(5\);
- \((1, 3)\) и \((3, 1)\);
- \((2, 4)\) и \((4, 2)\);
- \((2, 6)\) и \((6, 2)\);
- \((3, 4)\) и \((4, 3)\);
- \((3, 6)\) и \((6, 3)\);
- \((5, 5)\).
В третьем примере все наборы могут быть поделены поровну, поскольку \(m = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
|
1
|
|
2
|
6 5
|
13
|
|
3
|
1000000000 1
|
1000000000000000000
|