You are given a grid $$A$$ that consists of $$N$$ rows and $$M$$ columns. Each number in the grid is either $$0$$ or $$1$$.

Calculate the number of such triples \((i, j, h)\) where for all the pairs \((x, y)\), both $$x$$ and $$y$$ belong to \([1, h]\) if \(y >= x\) and \(A[i+x-1][j+y-1]\) equals to $$1$$. Of course, the square \((i, j, i+h-1, j+h-1)\) should be inside of this grid. In other words, calculate the count of square submatrices of the given grid $$A$$ which have their value equal to $$1$$ for every element present on and above their main diagonal.

Input format

• The first line contains an integer $$T$$ denoting the number of test cases.
• The first line of each testcase contains two space-separated integers $$N$$ and $$M$$ denoting the size of the grid $$A$$.
• The following $$N$$ lines describe the grid. Each line consists of $$M$$ characters that are either $$0$$ or $$1$$.

Output format

For each test case, print the count of square submatrices in a new line.

Constraints