#include <algorithm> #include <iostream> #include <numeric> #include <set> #include <string> #include <unordered_map> #include <utility> #include <vector> using namespace std; using i64 = long long; unordered_map<char, pair<int, int>> headings { { 'U', { -1, 0 } }, { 'D', { 1, 0 } }, { 'L', { 0, -1 } }, { 'R', { 0, 1 } } }; inline pair<int, int>& operator+=(pair<int, int>& lhs, const pair<int, int>& rhs) { lhs.first += rhs.first; lhs.second += rhs.second; return lhs; } inline pair<int, int> operator+(pair<int, int> lhs, pair<int, int> rhs) { return lhs += rhs; } inline char reverse(char ch) { if (ch == 'R') return 'L'; else if (ch == 'L') return 'R'; else return 'U' + 'D' - ch; } struct Solution { int n, m, k; string s; bool is_inside(const pair<int, int>& pos) { return 0 <= pos.first && pos.first < n && 0 <= pos.second && pos.second < m; } void main() { cin >> n >> m >> k >> s; if (n <= 100 && m <= 100 && s.size() <= 100) { vector<vector<int>> cnts(n, vector<int>(m)); k = n * m - k; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { pair<int, int> cur { i, j }; set<pair<int, int>> path { cur }; bool fail = false; for (auto c : s) { cur += headings[c]; if (!is_inside(cur)) { fail = true; break; } path.insert(cur); } if (fail) { --k; continue; } for (auto each : path) ++cnts[each.first][each.second]; } } int ans = 0; for (const auto& cnt : cnts) ans += count(cnt.begin(), cnt.end(), k); cout << ans << '\n'; } else { int x1 = 0, x2 = 0, y1 = 0, y2 = 0; pair<int, int> cur { 0, 0 }; vector<pair<int, int>> path { cur }; for (auto c : s) { cur += headings[c]; int x = cur.first, y = cur.second; path.emplace_back(-x, -y); x1 = min(x1, x); x2 = max(x2, x); y1 = min(y1, y); y2 = max(y2, y); } x1 = -x1; y1 = -y1; x2 = n - x2 - 1; y2 = n - y2 - 1; k = (y2 - y1 + 1) * (x2 - x1 + 1) - k; auto is_useful = [&](const pair<int, int>& pos) { return x1 <= pos.first && pos.first <= x2 && y1 <= pos.second && pos.second <= y2; }; for (auto& c : s) c = reverse(c); int now = 0; vector<vector<int>> vis(n, vector<int>(m)); auto count = [&](int x, int y) { ++now; int res = 0; for (auto each : path) { cur = each + make_pair(x, y); if (!is_inside(cur)) continue; int now_x = cur.first, now_y = cur.second; if (vis[now_x][now_y] == now) continue; vis[now_x][now_y] = now; res += is_useful(cur); } return res; }; int ans = 0; vector<int> idx(m); iota(idx.begin(), idx.end(), 0); for (int i = 0; i < n; ++i) { ans += partition_point(idx.begin(), idx.begin() + (m >> 1), [&](int j) { return count(i, j) <= k; }) - partition_point(idx.begin(), idx.begin() + (m >> 1), [&](int j) { return count(i, j) < k; }) + partition_point(idx.begin() + (m >> 1), idx.end(), [&](int j) { return count(i, j) >= k; }) - partition_point(idx.begin() + (m >> 1), idx.end(), [&](int j) { return count(i, j) > k; }); } cout << ans << '\n'; } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; while (t-- > 0) Solution().main(); cout << flush; return 0; }