Cho 2 xâu ký tự X = x1, x2, .., xm và Y = y1, y2, …, yn. Cần xây dựng xâu T = t1, t2, t3, ..,tn+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(tk, tk+1 )) với k = 1, 2, ..,  n+m-1; trong đó, các chi phí c(tk, tk+1) được tính như sau:

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

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(xi, y1), c(xi, y2), …, c(xi, yn), 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