#include <cstdio>#include <algorithm>using namespace std;char mp[128][128];int dp[256][128][128];int main() { int re, w, h, n, l, r; scanf("%d", &re); for (int ri = 1; ri <= re; ++ri) { scanf("%d%d", &w, &h); for (int i = 1; i <= h; ++i) { scanf("%s", mp[i] + 1); } n = w + h; for (int k = 2; k <= n; ++k) { l = max(1, k - w); r = min(h + 1, k); for (int i = l - 1; i <= r; ++i) { for (int j = l - 1; j <= r; ++j) { dp[k][i][j] = -1; } } if (k == 2) { dp[2][1][1] = (mp[1][1] == '*'); } for (int i = l; i < r; ++i) { for (int j = l; j < r; ++j) { if (mp[i][k - i] == '#' || mp[j][k - j] == '#') { continue; } else { dp[k][i][j] = max( max(dp[k - 1][i][j], dp[k - 1][i][j - 1]), max(dp[k - 1][i - 1][j], dp[k - 1][i - 1][j - 1]) ); } if (dp[k][i][j] == -1) { continue; } if (mp[i][k - i] == '*') { ++dp[k][i][j]; } if (j != i && mp[j][k - j] == '*') { ++dp[k][i][j]; } } } } printf("%dn", dp[n][h][h]); }}
