Існує $n$ типів хлопців та $2 \cdot n$ дівчат. Типи хлопців пронумеровані цілими числами від $1$ до $n$, а дівчата пронумеровані цілими числами від $1$ до $2 \cdot n$.

Хлопців $i$-го типу є $c_i$, причому кожному з них подобаються дівчата з номерами $a_i$ та $b_i$.

Знайдіть розмір найбільшої множини хлопців такої, що для кожної пари хлопців з цієї множини існує хоча б одна дівчина, яка подобається їм обом.

У цій задачі кожен тест містить кілька наборів вхідних даних. Вам потрібно розв'язати задачу незалежно для кожного такого набору.

Вхідні дані

У першому рядку задано одне ціле число $T$ $(1 \le T \le 500)$~--- кількість наборів вхідних даних. Далі задано опис наборів вхідних даних.

У першому рядку кожного набору вхідних даних задано одне ціле число $n$ $(1 \le n \le 7 \cdot 10^5)$.

У наступних $n$ рядках задано по три цілі числа $a_i$, $b_i$, $c_i$ $(1 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9)$~--- параметри відповідного типу хлопців.

Гарантується, що $a_i \ne a_j$ або $b_i \ne b_j$ для будь-яких $1 \le i < j \le n$.

Гарантується, що сума $n$ по всім наборам вхідних даних одного тесту не перевищує $7 \cdot 10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть в окремому рядку одне ціле число~--- розмір найбільшої множини хлопців такої, що для кожної пари хлопців з цієї множини існує хоча б одна дівчина, яка подобається їм обом.

Приклади

Вхідні дані

3
2
1 2 3
3 4 5
5
1 2 1
1 3 4
4 5 2
3 4 2
1 4 3
4
1 2 3
2 3 4
3 5 4
1 3 2

Відповідь

5
9
10

Оцінювання

Нехай $S$~--- сума $n$ по всім наборам вхідних даних одного тесту, а $K$~--- сума всіх $c_i$ по всім наборам вхідних даних одного тесту.

1. ($5$ балів): $n \le 5$;
2. ($11$ балів): $S \le 100$;
3. ($7$ балів): кожна дівчина подобається хлопцям не більше ніж двох типів;
4. ($10$ балів): $S \le 3000$;
5. ($23$ бали): $S \le 3 \cdot 10^5$;
6. ($19$ балів): $K \le 10^7$;
7. ($25$ балів): без додаткових обмежень.