I. 「I」nan desu
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In life, everyone is foolish in a lovely way

After struggling hard, the rain stops and the sky clears, yes

This is a light never seen before in human history

This is「I」——

A painting by enana can be represented by a black-and-white grid of size $$$n \times m$$$. She calls a subrectangle in the painting an「I」if and only if it satisfies the following conditions:

  • The number of columns is odd;
  • Both the number of rows and the number of columns are at least $$$3$$$;
  • The middle column is all black;
  • The first row and the last row are all black.

Cells not limited by these conditions may be of any color.

Your task is to help her count the number of「I」s in the painting.

Input

Each test file contains multiple test cases. The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, the number of test cases.

For each test case, the first line contains two integers $$$n,m$$$ $$$(3 \leq n,m \leq 2 \times 10^5)$$$, denoting the number of rows and columns of the painting.

Then follows a character matrix of size $$$n \times m$$$, consisting of * and ., representing the black and white cells of the painting.

It is guaranteed that the sum of $$$n \times m$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output one line containing one integer, the number of「I」s in the painting.

Example
Input
2
4 4
***.
.***
***.
.***
3 5
*****
.***.
*****
Output
2
4
Note

In Sample 1, there are exactly $$$2$$$「I」s: