Tin học trẻ 2022 - Vòng Sơ khảo - bảng B

Dãy cấp số nhân

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bài 1: Dãy cấp số nhân

Bảng ký tự

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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

Test 1

Input