给定一个 0-1 矩形矩阵。其中有多少个正方形?正方形是线宽等于 1 的实心正方形框架(边框)。正方形应至少为 2 × 2。我们只对两种类型的正方形感兴趣:
1. 每条边与矩阵的一条边平行的正方形;
2. 每条边平行于矩阵对角线的正方形。
无论哪种类型,一个正方形必须至少包含一个 1,并且不能接触(边或角)任何外来 1。当然,每个正方形的边长应该相等。
给定矩阵中有多少个方格?
输入
第一行包含整数 t (1 ≤ t ≤ 10000),其中 t 是输入中测试用例的数量。然后是测试用例。每个案例都以包含整数 n 和 m (2 ≤ n, m ≤ 250) 的行开始,其中 n 是行数,m 是列数。以下 n 行每行包含 m 个字符(0 或 1)。
对于任何输入文件,所有测试用例中的字符总数不超过 106。
输出
您应该准确输出 t 行,并在第 i 行输出第 i 个测试用例的答案。
示例
输入 #1
2 8 8 00010001 00101000 01000100 10000010 01000100 00101000 11010011 11000011 10 10 1111111000 1000001000 1011001000 1011001010 1000001101 1001001010 1010101000 1001001000 1000001000 1111111000
输出 #1
1 2
输入 #2
1 12 11 11111111111 10000000001 10111111101 10100000101 10101100101 10101100101 10100000101 10100000101 10111111101 10000000001 11111111111 00000000000
输出 #2
3