#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<fstream>
#include<bitset>
using namespace std;
vector<vector<bool> > v;
vector<vector<bool> > visited;
long long c;
long long n, m;
long long moveX[] = { 0,1,0,-1 };
long long moveY[] = { 1,0,-1,0 };
void dfs(long long i, long long j)
{
if (visited[i][j])
return;
if (v[i][j] == 0)
return;
visited[i][j] = true;
c++;
for (long long k = 0; k < 4; k++)
{
long long a = i + moveX[k];
long long b = j + moveY[k];
if (a < 0 || a >= n || b < 0 || b >= m)
continue;
dfs(a, b);
}
}
int main()
{
ifstream cin("zamalek.in");
long long t;
cin >> t;
while (t--)
{
long long x, k;
cin >> x >> k >> n >> m;
v.assign(n, vector<bool>(m));
for (long long i = 0; i < n; i++)
{
for (long long j = 0; j < m; j++)
{
char ch;
cin >> ch;
v[i][j] = (ch == '.');
}
}
long long ans = 0;
visited.assign(n, vector<bool>(m, 0));
for (long long i = 0; i < n; i++)
{
for (long long j = 0; j < m; j++)
{
if (visited[i][j] || v[i][j]==0)
continue;
c = 0;
dfs(i, j);
long long groups = c / k;
groups = min(groups, x);
ans += groups * k;
x -= groups;
}
}
cout << ans << endl;
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8cXVldWU+CiNpbmNsdWRlPGZzdHJlYW0+CiNpbmNsdWRlPGJpdHNldD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp2ZWN0b3I8dmVjdG9yPGJvb2w+ID4gdjsKdmVjdG9yPHZlY3Rvcjxib29sPiA+IHZpc2l0ZWQ7CmxvbmcgbG9uZyBjOwpsb25nIGxvbmcgbiwgbTsKIApsb25nIGxvbmcgbW92ZVhbXSA9IHsgMCwxLDAsLTEgfTsKbG9uZyBsb25nIG1vdmVZW10gPSB7IDEsMCwtMSwwIH07CiAKdm9pZCBkZnMobG9uZyBsb25nIGksIGxvbmcgbG9uZyBqKQp7CglpZiAodmlzaXRlZFtpXVtqXSkKCQlyZXR1cm47CglpZiAodltpXVtqXSA9PSAwKQoJCXJldHVybjsKCXZpc2l0ZWRbaV1bal0gPSB0cnVlOwoJYysrOwoJZm9yIChsb25nIGxvbmcgayA9IDA7IGsgPCA0OyBrKyspCgl7CgkJbG9uZyBsb25nIGEgPSBpICsgbW92ZVhba107CgkJbG9uZyBsb25nIGIgPSBqICsgbW92ZVlba107CgkJaWYgKGEgPCAwIHx8IGEgPj0gbiB8fCBiIDwgMCB8fCBiID49IG0pCgkJCWNvbnRpbnVlOwoJCWRmcyhhLCBiKTsKCX0KfQogCmludCBtYWluKCkKewoJaWZzdHJlYW0gY2luKCJ6YW1hbGVrLmluIik7Cglsb25nIGxvbmcgdDsKCWNpbiA+PiB0OwoJd2hpbGUgKHQtLSkKCXsKCQlsb25nIGxvbmcgeCwgazsKCQljaW4gPj4geCA+PiBrID4+IG4gPj4gbTsKCQl2LmFzc2lnbihuLCB2ZWN0b3I8Ym9vbD4obSkpOwogCgkJZm9yIChsb25nIGxvbmcgaSA9IDA7IGkgPCBuOyBpKyspCgkJewoJCQlmb3IgKGxvbmcgbG9uZyBqID0gMDsgaiA8IG07IGorKykKCQkJewoJCQkJY2hhciBjaDsKCQkJCWNpbiA+PiBjaDsKCQkJCXZbaV1bal0gPSAoY2ggPT0gJy4nKTsKCQkJfQoJCX0KIAoJCWxvbmcgbG9uZyBhbnMgPSAwOwoJCXZpc2l0ZWQuYXNzaWduKG4sIHZlY3Rvcjxib29sPihtLCAwKSk7CgkJZm9yIChsb25nIGxvbmcgaSA9IDA7IGkgPCBuOyBpKyspCgkJewoJCQlmb3IgKGxvbmcgbG9uZyBqID0gMDsgaiA8IG07IGorKykKCQkJewoJCQkJaWYgKHZpc2l0ZWRbaV1bal0gfHwgdltpXVtqXT09MCkKCQkJCQljb250aW51ZTsKCQkJCWMgPSAwOwoJCQkJZGZzKGksIGopOwoJCQkJbG9uZyBsb25nIGdyb3VwcyA9IGMgLyBrOwoJCQkJZ3JvdXBzID0gbWluKGdyb3VwcywgeCk7CgkJCQlhbnMgKz0gZ3JvdXBzICogazsKCQkJCXggLT0gZ3JvdXBzOwoJCQl9CgkJfQogCgkJY291dCA8PCBhbnMgPDwgZW5kbDsKCX0KIAoJcmV0dXJuIDA7Cn0=