有一些題目會請你找出有多少個不同大小的長方形(或者是圓形,三角形等)。這個題目要求在一個長方形的板子中有多少個子長方形(正方形也算長方形的一種)。
給定一個長方形的板子,n 列 m 行個 0 和 1。我們想要算出有多少個子長方形(包括正方形)由 1 所組成。
Input
輸入包涵很多測資,每個測資的第一行和第二行指出這個板子有幾列(n) 幾行(m) 。接下來輸入的 n 行表示出這個板子,每一列皆由 0 和 1 組成(不包含空白)。當板子的任一邊長為 0 時代表檔案的結束。測試資料中,板子兩邊長度不會超過 100。
Output
每一組測資輸出一行為有多少個長方形。測資和測資間不需要空白行隔開。
舉個列子,如下板子:
11
01
其所有的長方形為:
1-
--
-1
--
--
-1
11
--
-1
-1
Sample Input
2 2 11 01 4 3 110 101 111 011 0
Sample Output
5 22