Luffy là một hải tặc chuẩn bị ra khơi với ước mơ chinh phục kho báu ONE PIECE . Ở ngoài biển, sức mạnh của hải tặc được thể hiện qua một giá trị nguyên duy nhất là haki.

Muốn chinh phục kho báu ONE PIECE thì Luffy phải vượt qua n đảo. Luffy có thể chọn thứ tự đi giữa các đảo và mỗi đảo chỉ đến đúng một lần. Để vượt qua một đảo thành công thì cậu ấy phải đánh bại hết đối thủ tại đảo đó. Khi Luffy đến đảo thứ i thì cậu ấy phải đánh ~k~_i đối thủ theo thứ tự: đầu tiên là đối thủ có ~h~_i,1 haki, tiếp theo là đối thủ có ~h~_i,2 haki,. . . cuối cùng là đối thủ có ~h~_i,ki haki.

Luffy chỉ có thể đánh bại đối thủ khi lượng haki của cậu ấy lớn hơn của đối thủ. Nếu như Luffy không đánh bại 1 đối thủ bất kì thì cậu ấy sẽ chết và kết thúc ước mơ chinh phục kho báu ONE PIECE của mình. Lưu ý rằng, Luffy khi đến một hòn đảo, cậu ấy không thể rời trước khi đánh bại hết đối thủ tại hòn đảo đó.

Mỗi khi đánh bại 1 đối thủ, haki của Luffy sẽ được tăng lên 1 đơn vị.

Với khát khao chinh phục kho báu, Luffy rất chăm chỉ luyện tập để đủ lượng haki và ra khơi vào một ngày không xa. Nhưng khổ nổi, cậu ấy không giỏi tính toán nên không biết bao nhiêu haki là đủ. Bạn hãy giúp Luffy tính lượng haki tối thiểu để cậu ấy có thể nhanh chóng ra khơi và chinh phục kho báu ONE PIECE nhé!

Input

• Dòng đầu tiên là 1 số nguyên T biểu thị số testcase (1 ≤ T ≤ 10⁵)
• Tiếp theo, với mỗi testcase gồm:
• Dòng đầu của testcase là 1 số nguyên n (1 ≤ n ≤ 10⁵) - số lượng đảo.
• n dòng tiếp theo. Tại dòng thứ i chứa số nguyên ki (1 ≤ ~k~_i ≤ 10⁵) - Số lượng đối thủ tại đảo thứ i, sau đó là ki số nguyên ~h~_i,1, ~h~_i,2,..., ~h~_i,ki (1 ≤ ~h~_i,j, ≤ 10⁹) – Lượng haki của từng đối thủ tại đảo thứ i.

Tổng của ki trên tất cả các testcase luôn đảm bảo không vượt quá 10⁵

Output

Với mỗi testcase, in ra một số nguyên duy nhất – lượng haki tối thiểu mà Luffy cần để vượt qua tất cả các hòn đảo và chinh phục kho báu ONE PIECE.