Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. How Many Squares?

time limit per test

2 secondsmemory limit per test

64 megabytesinput

standard inputoutput

standard outputYou 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:

- squares with each side parallel to a side of the matrix;
- 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 10^{6} 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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2021 21:57:31 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|