Attempt

Please login to see your submissions result.

Problem

Sau khi Nữ Thần Mùa Xuân biến mất, Vương điện Laucaria mở Mê Lộ Bích Họa – một cung điện phẳng gồm ~n~ hàng và ~m~ cột. Tế quan phải lần theo đường đi đã khắc sẵn trên nền đá theo kiểu con rắn. Biết rằng mỗi bước đi đều mất ~k~ đồng tế phẩm.

Trên mỗi ô có thể ẩn một bùa chú độc. Bảng nghi thức ghi bằng chữ cổ: trên đường đi, hễ đặt chân lên ô có bùa độc thì phải quay về Đài Tẩy Uế gần nhất trước đó để làm lễ để hóa giải (khi làm lễ thì không mất tiền). Đài Tẩy Uế luôn nằm ở đầu của một hàng mà đã đến.

Hãy tính tổng chi phí tế phẩm tối thiểu để hoàn thành nghi thức cho toàn bộ mê lộ.

Chú ý: Tế quan sẽ đi theo kiểu con rắn tức là đi hết hàng 1, rồi đi đến cuối hàng 2, rồi lên đầu hàng 2, rồi sang đầu hàng 3... Khi tế quan tới hàng chẵn mà đang nhiễm bùa độc, thì tế quan chưa biết rằng có bùa độc nữa ở đằng trước không nên sẽ về hàng trước chữa trị. Ở các hàng lẻ thì tế quan sẽ luôn về đầu hàng để chữa trị.

Input

Dòng đầu là số bộ test ~t~.
Mỗi test gồm một dòng chứa ba số nguyên ~n, m, k~ ~(1 < n, m, k < 100)~.
Tiếp theo là ~n~ dòng, mỗi dòng có ~m~ ký tự 0 hoặc 1:

• 0 nghĩa là ô an toàn,
• 1 nghĩa là ô có bùa độc.

Output

Với mỗi test, in ra tổng chi phí tế phẩm cần thiết để đi theo lộ trình hình rắn và hoàn tất nghi thức.

Sample