Masala #1203

Xotira 64 MB Vaqt 1000 ms
14

Connecting game

Pokemon o'yinlari orasida "Connect animals" nomli ajoyib o'yin mavjud. O'yin shartiga ko'ra sizga hayvonlar rasmlari tushirilgan kartalar to'g'ri to'rtburchak ko'rinishida taxlangan holatda beriladi. Siz 2 ta bir xil rasmli kartalarni birlashtirish orqali o'yindan chiqarib yuborishingiz mumkin, hamma kartalarni chiqarib yuborganingizdan keyin o'yin yakuniga yetadi. 2 ta bir xil rasmli kartani birlashtirish uchun kartalar orasidagi yo'lda ko'pi bilan 2 ta burilish bo'lishi mumkin. 2 tadan ko'p bo'lgan holatda yoki kartalar orasida yo'l bo'lmagan holatda kartalarni o'yindan chiqara olmaysiz. Kartalar orasidagi yo'l boshqa karta ustidan o'tishi yoki diagonal bo'yicha o'tishi mumkin emas. O'yinni o'ynab ko'rish uchun link.
 


Sizga NxM o'lchamdagi o'yin maydoni beriladi. O'yin maydonidagi har bir katak ingliz alifbosining kichik harflari yoki . (nuqta) belgisidan iborat bo'lishi mumkin. Bunda harflar hayvonlarni, . belgisi esa bo'sh katakni ifodalaydi. Bir xil harflar bir xil hayvonlarni ifodalaydi. Shu berilgan o'yin holatida nechta birlashtirish imkoniyati borligini aniqlang.


Kiruvchi ma'lumotlar:

Birinchi qatorda N va M natural sonlari. (2<=N,M<=10)
   Keyingi N ta qatorda M tadan belgi, o'yin maydonidagi holat beriladi.


Chiquvchi ma'lumotlar:

Berilgan o'yin holatidagi birlashtirish imkoniyatlari soni.


Misollar
# input.txt output.txt
1
3 3
...
a.a
...
1
2
3 3
a.a
a.a
a.a
15
3
1 3
aaa
3