Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Sau khi phá tan lũ quái vật ở vùng biên giới, nhà vua quyết định mở cuộc tấn công tới tận hang ổ của bọn chúng. Hệ thống phòng thủ của lũ quái vật rất kiên cố và phức tạp. Bọn chúng xây dựng các lâu đài, và giữa một số cặp lâu đài, chúng đắp thành lũy liên kết với nhau, để bảo vệ cho các đội quân nằm bên trong. Hang ổ của quân địch cứ tầng tầng lớp lớp.

Nhà vua đã vạch ra kế hoạch như sau:

Bước 1: Dùng máy bắn đá phá vỡ một số thành trì liên kết giữa các lâu đài của bọn chúng, sao cho không có đội quân nào của địch được bảo vệ kín bởi hệ thống thành trì.

Bước 2: Tiến công đánh giáp lá cà với quân địch.

Trong các lâu đài, lũ quái vật chuẩn bị rất nhiều các máy bắn đá. Để đảm báo phá được một thành lũy, nhà vua yêu cầu cần sử dụng số máy bắn đá bằng với tổng số máy bắn đá mà hai lâu đài ở 2 đầu thành lũy của địch. Chẳng hạn nếu lâu đài A có 5 máy bắn đá, lâu đài B có 3 máy bắn đá, để phá được bức tường thành nối lâu đài A và lâu đài B, đội quân của nhà vua cần sử dụng ít nhất 5+3 = 8 máy bắn đá.

Hình vẽ minh họa cho một hệ thống lâu đài + thành lũy của quân địch. Khi phá bức tường thành liên kết giữa 2 cặp lâu đài có số lượng máy bắn đá là (1,1), sẽ sử dụng số máy bắn đá là ít nhất (4 cái). Khi đó, không còn đội quân nào được bao bọc kín bởi thành lũy nữa, quân đội của nhà vua sẽ sẵn sàng vào tấn công giáp lá cà.

Các bạn hãy giúp nhà vua tính toán xem, cần sử dụng ít nhất bao nhiêu máy bắn đá để thực hiện được bước 1 của chiến dịch.

Input

Dòng đầu tiên là số lượng bộ test T (1 <= T <= 10).

Mỗi test gồm dòng đầu tiên gồm số nguyên m (2 <= m <= 100) là số lâu đài của quân địch.

Mỗi thành được biểu diễn bởi 2 dòng. Dòng đầu tiên gồm 3 số nguyên i (0 <= i <= m-1), u_i (1 <= u_i <= 50), c_i (1 <= c_i <= m-1) lần lượt là số hiệu của lâu đài, số máy bắn đá của địch có trong lâu đài và số thành lũy liên kết tới các lâu đài khác.

Dòng thứ hai gồm c_i số, thể hiện các lâu đài có thành lũy liên kết tới lâu đài i.

Output

Với mỗi test, in ra tổng số số máy bắn đá ít nhất cần sử dụng để thực hiện bước 1 của chiến dịch.

Example

Input:
1
3
0 1 2
1 2
1 2 2
0 2
2 3 2
0 1

Output:
3