Bərabəryanlı üçbucaqlar
Fermer Conun otlağı, n × n ölçüsündə bir kvadrat şəbəkə ilə təsvir edilir və bu şəbəkə bütün (i, j) mövqeləri üçün (1 ≤ i, j ≤ n) mövqelərindən ibarətdir. Hər bir kvadratın uyğun simvolu giriş məlumatlarında '*' ilə göstərilir, əgər bu mövqedə bir inək varsa, və '.' ilə göstərilir, əgər bu mövqedə inək yoxdursa.
Con hesab edir ki, onun otlağının gözəlliyi, bir-birindən bərabər məsafədə olan üç inəyin sayına birbaşa mütənasibdir. Başqa sözlə, onlar bərabəryanlı üçbucaq əmələ gətirirlər. Təəssüf ki, Con yalnız yaxınlarda başa düşdü ki, bütün inəkləri tam ədədlərlə yerləşdirildiyi üçün, heç bir gözəl üçlük mövcud ola bilməz, əgər Evklid məsafəsi istifadə edilərsə! Beləliklə, Con "Manhetten" məsafəsinə keçməyə qərar verdi. Formal olaraq, iki mövqe arasındakı manhetten məsafəsi (x[0], y[0]) və (x[1], y[1]) |x[0] − x[1]| + |y[0] − y[1]| bərabərdir.
Verilən şəbəkədə inəklərin mövqeyinə əsasən bərabəryanlı üçbucaqların sayını hesablayın.
Giriş Məlumatları
Birinci sətir bir tam ədəd n (1 ≤ n ≤ 300) ehtiva edir. Hər bir i üçün (1 ≤ i ≤ n) i + 1 sətiri yalnız '*' və '.' simvollarını ehtiva edən uzunluğu n olan bir sətir ehtiva edir. j-ci simvol, mövqedə (i, j) inəyin olub-olmadığını göstərir.
Çıxış Məlumatları
Tək bir tam ədəd çıxarın, cavabı ehtiva edən. Məlumdur ki, bu cavab 32-bit imzalı tam ədədə sığır.
Nümunə
Üç inək var və onlar bərabəryanlı üçbucaq əmələ gətirirlər, çünki hər bir inək cütü arasındakı manhetten məsafəsi ikiyə bərabərdir.