11_C. How Many Squares?_33356
You are given a 0-1 rectangular matrix. What is the number of squares in it? A square is a solid square frame (border) with linewidth equal to 1. A square should be at least 2 × 2. We are only interested in two types of squares: 

  1. squares with each side parallel to a side of the matrix; 
  2. squares with each side parallel to a diagonal of the matrix. 


    
    
      
    For example the following matrix contains only one square of the first type:   
    0000000   
    0111100   
    0100100   
    0100100   
    0111100  
    
    
    
      
    The following matrix contains only one square of the second type:  
    0000000  
    0010000  
    0101000  
    0010000  
    0000000  
    

Regardless of type, a square must contain at least one 1 and can't touch (by side or corner) any foreign 1. Of course, the lengths of the sides of each square should be equal.

How many squares are in the given matrix?

Input

The first line contains integer t (1 ≤ t ≤ 10000), where t is the number of test cases in the input. Then test cases follow. Each case starts with a line containing integers n and m (2 ≤ n, m ≤ 250), where n is the number of rows and m is the number of columns. The following n lines contain m characters each (0 or 1).

The total number of characters in all test cases doesn't exceed 106 for any input file.

Output

You should output exactly t lines, with the answer to the i-th test case on the i-th line.

Examples

Input

2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000


Output

1
2


Input

1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000


Output

3
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const long long Linf = (1uLL << 63) - 1;
const double EPS = 1e-10;
namespace IOSpace {
void get_int(int &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-'; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
}
void get_int(long long &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-'; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
}
void print_int(int x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
void print_int(long long x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
}  // namespace IOSpace
using namespace IOSpace;
const int maxn = 253;
const int maxlog = 20;
const long long mod = 1000000007;
char s[maxn][maxn];
int n, m, ans, cnt;
pair<int, int> q[maxn * maxn], down;
int use[maxn][maxn], kk;
void dfs(int x, int y) {
  if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '0' || use[x][y]) return;
  use[x][y] = kk;
  ++cnt;
  down = max(down, make_pair(x, y));
  dfs(x - 1, y - 1);
  dfs(x - 1, y + 1);
  dfs(x + 1, y - 1);
  dfs(x + 1, y + 1);
  dfs(x - 1, y);
  dfs(x + 1, y);
  dfs(x, y - 1);
  dfs(x, y + 1);
}
void solve() {
  ans = kk = 0;
  get_int(n), get_int(m);
  memset((use), (0), sizeof(use));
  int len, ok;
  for (int i = 0; i < n; i++) scanf("%s", s[i]);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (!use[i][j] && s[i][j] == '1') {
        kk++;
        cnt = 0;
        down = make_pair(-1, -1);
        dfs(i, j);
        if (down.first == i) continue;
        if (down.second == j && ((down.first - i) & 1) == 0) {
          len = down.first - i;
          if (len << 1 != cnt) continue;
          ok = 1;
          for (int ii = 0; ii + ii <= len && ok; ii++) {
            ok &= (j - ii >= 0 && use[i + ii][j - ii] == kk &&
                   use[down.first - ii][j - ii] == kk);
            ok &= (j + ii < m && use[i + ii][j + ii] == kk &&
                   use[down.first - ii][j + ii] == kk);
          }
          ans += ok;
        } else if (down.second - j == down.first - i) {
          len = down.first - i;
          if (len << 2 != cnt) continue;
          ok = 1;
          for (int ii = 0; ii <= len && ok; ii++) {
            ok &= use[i][j + ii] == kk;
            ok &= use[down.first][j + ii] == kk;
            ok &= use[i + ii][j] == kk;
            ok &= use[i + ii][down.second] == kk;
          }
          ans += ok;
        }
      }
  printf("%d\n", ans);
}
int main() {
  int T;
  get_int(T);
  while (T--) solve();
  return 0;
}
