Cho bảng chữ kích thước \(m \cdot n\), mỗi ô chứa một kí tự \(A\) hoặc \(B\). Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc \(k\) nếu số lượng kí tự \(A\) và số lượng kí tự \(B\) trong bảng con chênh lệch không quá \(k\).

Yêu cầu

Cho bảng chữ kích thước \(m \cdot n\) và số nguyên \(k\), hãy tìm bảng con là bảng đẹp lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T(T \leq 5)\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:
• Dòng đầu chứa ba số nguyên \(m, n, k\).
• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\) chỉ gồm kí tự \(A\) hoặc \(B\).

Output

• Ghi ra thiết bị ra chuẩn \(T\) dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được
  tương ứng với dữ liệu vào.

Scoring

• Có \(25\)% số điểm của bài có \(m \cdot n \leq 100\).
• Có \(25\)% số điểm của bài có \(m \cdot n \leq 2000\).
• Có \(25\)% số điểm của bài có \(m \cdot n \leq 40000, k = 0\).
• Có \(25\)% số điểm của bài có \(m \cdot n \leq 60000\).

Example

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

8
9