Cho lưới hình chữ nhật ~m \times n~ ô vuông. Mỗi ô được đánh dấu là 'A' hoặc 'B'. Một khu vực cân bằng là một hình chữ nhật con sao cho số lượng ô loại 'A' và số lượng ô loại 'B' trong khu vực đó chênh lệch không quá ~k~, với ~k~ là hằng số cho trước.

Yêu cầu: Hãy tìm khu vực cân bằng có số lượng ô vuông lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ dữ liệu ~(1 \le T \le 6)~.

• ~T~ nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng với một bộ dữ liệu có định dạng:

  • Dòng đầu tiên chứa ba số nguyên ~m, n, k~ ~(1 < m \times n \le 60000;\ 0 \le k \le 1000)~.

  • ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ ký tự liên tiếp, chỉ gồm 'A', 'B'.

Các số trên cùng dòng được ghi cách nhau một dấu cách.

Output

Gồm ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả tương ứng của mỗi bộ dữ liệu. Nếu không tìm được khu vực cân bằng thì ghi số 0.

Scoring

Sample Input 1

2
3 5 0
AAAAB
BBBBA
BAAAA
3 4 1
AAAA
BBBB
BAAA

Sample Output 1

10
9

Notes

Test 1: Số lượng ô lớn nhất trong khu vực cân bằng có loại 'A', 'B' bằng nhau là ~10~ ô (hình chữ nhật có ~2~ hàng ~5~ cột).

Test 2: Số lượng ô lớn nhất trong khu vực cân bằng có độ chênh lệch loại 'A', 'B' không quá ~1~ là ~9~ ô (hình chữ nhật có ~3~ hàng ~3~ cột).