Рівносторонні трикутники
Пасовище фермера Джона можна уявити як квадратну сітку розміром n × n, що складається з позицій (i, j) для всіх i, j (1 ≤ i, j ≤ n). У кожній клітинці сітки символ у вхідних даних буде '*', якщо на цій позиції знаходиться корова, і '.', якщо корови немає.
Фермер Джон вважає, що краса його пасовища залежить від кількості трійок корів, які розташовані на однаковій відстані одна від одної, тобто утворюють рівносторонній трикутник. Проте, Джон нещодавно зрозумів, що через те, що всі його корови розташовані в цілочисельних координатах, жодні красиві трійки не можуть існувати, якщо використовувати евклідову відстань! Тому він вирішив використовувати манхеттенську відстань. Формально, манхеттенська відстань між двома позиціями (x[0], y[0]) і (x[1], y[1]) визначається як |x[0] − x[1]| + |y[0] − y[1]|.
За заданою сіткою з положенням корів, обчисліть кількість рівносторонніх трикутників.
Вхідні дані
Перша стрічка містить одне ціле число n (1 ≤ n ≤ 300). Для кожного i (1 ≤ i ≤ n) стрічка i + 1 містить рядок довжини n, що складається лише з символів '*' і '.'. j-й символ вказує, чи є корова на позиції (i, j).
Вихідні дані
Виведіть одне ціле число, яке є відповіддю. Відомо, що воно вміщується в 32-бітне ціле число зі знаком.
Приклад
Є три корови, які утворюють рівносторонній трикутник, оскільки манхеттенська відстань між кожною парою корів дорівнює двом.