#include "bits/stdc++.h" using namespace std; #define dbg(var) cout<<#var<<"="<<var<<" " #define nl cout<<"\n" #define fr(i,n) for(int i=0;i<n;i++) #define rep(i,a,n) for(int i=a;i<=n;i++) #define vi vector<int> #define pb push_back #define all(v) v.begin(),v.end() #define sz(v) (int)(v.size()) //#define int long long #define kill(x) { cout << x << " "; return ;} vector<int> get (vector<int> & s,int n){ vector<int> d1(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) { k++; } d1[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } return d1; } int find(vector<int> &v){ int n = v.size(); int r[n]{}; int j = 0; int ans = 0; for(int i = 1 ; i < n; i++){ j = max(i,j); if(!v[i]) continue; ///0 1 2 2 3 4 if(r[i-1]){ r[i] = r[i-1] - 1; } while(j < n and v[j] >= j - i + 1){ j++; r[i]++; } ans += r[i]; } return ans; } void solve(){ int n,m; cin >> n >> m; string s[n]; fr(i,n) cin >> s[i]; vector<int> grid[n+5],rd[n+5]; int cnt = 2; fr(i,n){ grid[i].resize(m+2); fr(j,m){ grid[i][j] = (s[i][j] == '*' ? 1 : ++cnt); } } vector<int> temp[m]; fr(i,m) temp[i].emplace_back(0); fr(i,n){ rd[i] = get(grid[i],m); fr(j,m){ if(s[i][j] == '.') rd[i][j] = 0; temp[j].emplace_back(rd[i][j]); // cout << rd[i][j] << " " ; } // nl; } int ans = 0; fr(i,m) ans += find(temp[i]); cout << ans << "\n"; } int32_t main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int tst; cin >> tst; while(tst--) { solve(); } }