Диас недавно начал изучать машинное обучение. Особенно сильно ему понравилась сфера распознавания различных паттернов в фотографиях. Недавно ему пришлось работать с распознаванием так называемых алмазов с некоторыми свойствами. Алмазы, по своей сути, имеют форму обычной квадратной рамки, повернутой на $$$45$$$ градусов.

Диас справился со своей задачей в машинном обучении. Теперь ему стало интересно, а смогут ли решить эту задачу наши любимые ACM-щики? Поскольку в машинном обучении люди работают с настоящими фотографиями у которых могут быть разные неровности и размытости, Диас адаптировал свою задачу специально для наших ребят: они могут считать, что фотография является бинарной матрицей размера $$$n \times n$$$. Строки и столбцы матрицы пронумерованы от $$$1$$$ до $$$n$$$.

Определим понятие алмазов в данной задаче более подробно. Каждый алмаз можно описать тремя положительными целыми числами — его центром $$$(p, q)$$$ и его радиусом $$$r$$$. Все клетки $$$(x, y)$$$, образующие сам алмаз, будут соответствовать свойству $$$|x - p| + |y - q| = r$$$. На картинке ниже приведены алмазы $$$(2, 2, 1)$$$, $$$(4, 3, 1)$$$ и $$$(3, 3, 2)$$$.

Диас попросил ACM-щиков посчитать общее количество алмазов на фотографии со следующими свойствами:

1. Алмаз находится полностью внутри матрицы. Более формально, все клетки $$$(x, y)$$$ принадлежащие алмазу соответствуют условию $$$1 \le x, y \le n$$$.
2. Все клетки алмаза содержат только единицы.

Вы были одним из тех ребят, которые услышали эту задачу напрямую из уст Диаса. Сможете её решить?