B. Подели конфеты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аркадий и его друзья любят играть в шашки на доске $$$n \times n$$$. Строки и столбцы доски пронумерованы от $$$1$$$ до $$$n$$$.

Друзья недавно выиграли какой-то турнир, поэтому Аркадий хочет поздравить их и подарить конфеты. Вспомнив старинную притчу (но не ее мораль), Аркадий решил дать друзьям по одному набору конфет за каждую клетку доски: набор конфет, соответствующий клетке $$$(i, j)$$$, будет состоять из ровно $$$(i^2 + j^2)$$$ конфет особенного для этой клетки типа.

Всего друзей, выигравших турнир, $$$m$$$. Сколько же из этих $$$n \times n$$$ наборов конфет можно разделить поровну на $$$m$$$ частей, не разделяя конфеты на части? Обратите внимание, что каждый набор нужно делить независимо, так как конфеты в разных наборах разные.

Входные данные

Единственная строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 1000$$$) — размер доски и количество частей, на которые нужно делить наборы.

Выходные данные

Выведите одно целое число — количество наборов, которые можно поделить поровну.

Примеры
Входные данные
3 3
Выходные данные
1
Входные данные
6 5
Выходные данные
13
Входные данные
1000000000 1
Выходные данные
1000000000000000000
Примечание

В первом примере только набор, соответствующий клетке $$$(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$$$.