Giải bài trực tuyến

Cho 2 xâu ký tự X = x₁, x₂, .., x_m và Y = y₁, y₂, ..., y_n. Cần xây dựng xâu T = t₁, t₂, t₃, ..,t_n+m. gồm tất cả các ký tự trong xâu X và tất cả các ký tự trong xâu Y, sao cho các ký tự trong X xuất hiện trong T theo thứ tự xuất hiện trong X và các ký tự trong Y xuất hiện trong T theo đúng thứ tự xuất hiện trong Y, đồng thời với tổng chi phí trộn là nhỏ nhất. Tổng chi phí trộn hai xâu X và Y để thu được xâu T được tính bởi công thức c(T) = sum(c(t_k, t_k+1 )) với k = 1, 2, ..,  n+m-1; trong đó, các chi phí c(t_k, t_k+1) được tính như sau:

• Nếu hai ký tự liên tiếp t_k, t_k+1 được lấy từ cùng một xâu X hoặc Y thì c(t_k, t_k+1) = 0
• Nếu hai ký tự liên tiếp t_k, t_k+1 là x_i y_j thì chi phí phải trả là c(x_i, y_j). Nếu hai ký tự liên tiếp t_k, t_k+1 là y_j, x_i thì chi phí phải trả là c(y_j, x_i) = c(x_i, y_j)

Input

Dòng đầu tiên chứa Q là số lượng bộ dữ liệu. tiếp đến là Q nhóm dòng, mỗi nhóm cho thong tin về 1 bộ dữ liệu theo khuôn dạng sau:

• Dòng thứ nhất chứa 2 số nguyên duong m, n (m, n <= 1000);
• Dòng thứ i trong m dòng tiếp theo chứa n số nguyên dương, mỗi số không vượt quá 10^9: c(x_i, y₁), c(x_i, y₂), …, c(x_i, y_n), i = 1, 2,…, m.

Ràng buộc : Có 60% số test ứng với 60% số điểm của bài đó có m, n <= 10

Output

• Gồm Q dòng, mỗi dòng chứa một số nguyên là tổng chi phí theo cách xây dựng xâu T tìm được tương ứng với bộ dữ liệu vào.

Example

Input:
1
2 3
3 2 30
15 5 4

Output:

6