B. Find the Spruce（递推）

are up soon. Rick that it’s time to think about a tree. But Rick doesn’t want real trees to get hurt so he to find some in an n×m of “" and “.”.

To find every first let’s what a in the is. A set of cells is a of k with at point (x,y) if:

All cells in the set an "”.

For each 1≤i≤k all cells with the row x+i−1 and in range [y−i+1,y+i−1] must be a part of the set. All other cells to the set.

of and trees:

Now Rick wants to know how many his n×m . Help Rick solve this .

Input

Each test one or more test cases. The first line the of test cases t (1≤t≤10).

The first line of each test case two n and m (1≤n,m≤500) — size.

Next n lines of each test case m ci,j — . It is that ci,j is a “.” or an “*”.

It is that the sum of n⋅m over all test cases does not 5002 (∑n⋅m≤5002).

For each test case, print — the total of in the .

input

2 3

.*.

2 3

..

4 5

..

..*

5 7

….…

.*****.

.*****.

….…

23

34

Note

In the first test case the first of 2 has its at point (1,2), the of 1 has its at point (1,2), the third of 1 has its at point (2,1), the of 1 has its at point (2,2), the fifth of 1 has its at point (2,3).

In the test case the first of 1 has its at point (1,2), the of 1 has its at point (2,1), the third of 1 has its at point (2,2).

#include 
typedef long long ll;
const ll mod = 9999999967;
using namespace std;
namespace fastIO {inline void input(int& res) {char c = getchar();res = 0;int f = 1;while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }res = f ? res : -res;}inline ll qpow(ll a, ll b) {ll ans = 1, base = a;while (b) {if (b & 1) ans = (ans * base % mod +mod )%mod;base = (base * base % mod + mod)%mod;b >>= 1;}return ans;}
}
using namespace fastIO;
const int N = 1e6 + 5;int Case,n,m;
char s[505][505];
int ans[505][505];int cal(int x,int y){int res = 0;int minn;ans[x][y]=1;if(x+1>n||y<2||y+1>m) return -1;minn = 0x3f3f3f3f;for(int i=y-1;i<=y+1;i++){minn = min(minn,ans[x+1][i]);}ans[x][y] += minn;return minn+1;
}void solve(){ll res = 0;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){getchar();scanf("%s",s[i]+1);}for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){if(s[i][j]=='*') {if(cal(i,j)==-1) {res++;continue;}res += cal(i,j);}}}printf("%lld\n",res);memset(ans,0,sizeof(ans));
}int main(){//init();Case=1;scanf("%d",&Case);while(Case--){solve();}return 0;
}