Cho ~2~ xâu ký tự ~X = x_{1}~, ~x_{2}~, ..., ~x_{m}~ và ~Y = y_{1}~, ~y_{2}~, ..., ~y_{n}~. Cần xây dựng xâu ~T = t_{1}~, ~t_{2}~, ~t_{3}~, ..., ~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\left(T\right) = \sum_{k = 1}^{n + m - 1}c\left(t_{k}, t_{k+1}\right)~; trong đó, các chi phí ~c\left(t_{k}, t_{k+1}\right)~ đượ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\left(t_{k}, t_{k+1}\right) = 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\left(x_{i}, y_{j}\right)~. 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\left(y_{j}, x_{i}\right) = c\left(x_{i}, y_{j}\right)~

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 \le 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\left(x_{i}, y_{1}\right)~, ~c\left(x_{i}, y_{2}\right)~, ..., ~c\left(x_{i}, y_{n}\right)~, ~i = 1~, ~2~, ..., ~m~.

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.

Giới hạn

Có 60% số test ứng với 60% số điểm của bài đó có ~m~, ~n \leq 10~

Sample Input

1
2 3
3 2 30
15 5 4

Sample Output

6