Hang Sâu Thẳm

Một anh hùng được đặc trưng bởi một số nguyên duy nhất: sức mạnh. Anh ta phải đánh bại các quái vật, mỗi quái vật cũng được đặc trưng bởi một số nguyên duy nhất: giáp.

Ở màn hiện tại, anh hùng đối mặt với $n$ hang động. Để qua màn, anh hùng phải đi vào tất cả các hang động theo một thứ tự nào đó, mỗi hang đúng một lần, và ra khỏi mỗi hang an toàn. Khi anh hùng vào hang $i$, anh ta phải lần lượt chiến đấu với $k_i$ quái vật: đầu tiên là quái vật có giáp $a_{i,1}$, rồi $a_{i,2}$, ..., cuối cùng là $a_{i,k_i}$.

Anh hùng đánh bại được một quái vật khi và chỉ khi sức mạnh của anh ta lớn hơn thực sự giáp của quái vật đó. Nếu không đánh bại được quái vật đang đối mặt thì trò chơi kết thúc và người chơi thua. Lưu ý rằng một khi đã vào hang, anh hùng không thể ra khỏi hang trước khi chiến đấu với toàn bộ quái vật trong hang đó, đúng theo thứ tự đã cho.

Mỗi lần đánh bại một quái vật, sức mạnh của anh hùng tăng thêm $1$.

Hãy tìm sức mạnh khởi đầu nhỏ nhất mà anh hùng cần có để có thể đi vào tất cả các hang theo một thứ tự nào đó và đánh bại mọi quái vật.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu chứa số nguyên $t$ , số lượng bộ test.

Với mỗi bộ test:

• Dòng đầu chứa số nguyên $n$ , số hang động.
• Dòng thứ $i$ trong $n$ dòng tiếp theo chứa số nguyên $k_i$ (số quái vật trong hang $i$), theo sau là $k_i$ số nguyên $a_{i,1},a_{i,2},\dots ,a_{i,k_i}$ , giáp của các quái vật trong hang $i$ theo thứ tự phải chiến đấu.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất: sức mạnh khởi đầu nhỏ nhất để anh hùng qua được màn.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le n\le {10}^5$
• $1\le k_i\le {10}^5$
• $1\le a_{i,j}\le {10}^9$
• Tổng $k_i$ trên tất cả các bộ test không vượt quá ${10}^5$.

Ví dụ