Một bảng số nguyên không âm được gọi là bảng đẹp nếu tổng các số trong bảng chia hết cho \(9\).
Ví dụ, bảng sau đây là một bảng đẹp:

Yêu cầu: Cho bảng số nguyên không âm kích thước \(m \times n\), hãy đếm bộ chỉ số \((x, y, u, v)\) với \(1 \le x \le u \le m\); \(1 \le y \le v \le n\) sao cho bảng số con có ô trái trên \((x, y)\) và ô phải dưới \((u, v)\) là một bảng đẹp.

Input

• Dòng đầu chứa số nguyên \(m, n\);
• Dòng thứ \(i\) \((1 \le i \le m)\) trong \(m\) dòng sau chứa \(n\) số nguyên \(a_{i, 1}, a_{i, 2}, \dots, a_{i, n}\) \((a_{i, j} \le 10^9)\).

Output

• Ghi ra một số nguyên là số bộ chỉ số \((x, y, u, v)\) thỏa mãn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m, n \le 10\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 500\).

Example

2 3
3 3 3
1 2 6

5

Trên một khoảng sân rộng có chiều dài \(L\), người ta đặt một số thùng hàng. Dưới đây là một hình ảnh về sân có chiều dài 10, có chứa 5 thùng hàng A, B, C, D, E.

Hoàng muốn di chuyển các thùng hàng để tạo ra một khoảng sân có độ rộng tối thiểu là \(W\) để có thể chơi bóng cùng các bạn của mình. Mỗi bước, Hoàng có thể di chuyển một thùng hàng sang trái hoặc sang phải nếu vị trí vẫn nằm trong sân và vị trí đó còn trống.
Với ví dụ trên, khi Hoàng cần một khoảng sân độ rộng tối thiểu là \(3\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(2\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(4\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(4\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(5\), thì dưới đây là một cách di chuyển các thùng
hàng. Cách di chuyển này cần \(7\) bước di chuyển.

Yêu cầu: Cho vị trí ban đầu của các thùng hàng và giá trị \(W\), bạn hãy giúp Hoàng tính số bước di chuyển ít nhất.

Input

• Dòng đầu tiên ghi số \(T\) là số bộ dữ liệu \((T \le 10)\)
• \(T\) dòng tiếp theo, mỗi dòng mô tả một bộ dữ liệu. Mỗi dòng chứa một xâu kí tự \(s\) mô tả sân có độ dài không quá \(5 × 10^5\) và số nguyên dương \(W\) cách nhau bởi dấu cách. Xâu kí tự \(s\) chỉ gồm dấu chấm hoặc kí tự \(X\), trong đó kí tự chấm thể hiện vị trí sân không có thùng hàng và kí tự \(X\) thể hiện vị trí sân có thùng hàng.

Output

• Ghi ra \(T\) dòng, mỗi dòng chứa một số nguyên là ra số lần di chuyển các thùng hàng ít nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50\) và có không quá \(3\) thùng hàng.
• Subtask \(2\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(20\).
• Subtask \(3\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50\).
• Subtask \(4\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(200\).
• Subtask \(5\) (\(25\%\) số điểm): độ dài xâu \(s\) không vượt quá \(5000\).
• Subtask \(6\) (\(20\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50000\).
• Subtask \(7\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Example

4
.XX..XX.X. 2
.XX..XX.X. 3
.XX..XX.X. 4
.XX..XX.X. 5

0
2
4
7