불안정한 물질

과학자 X는 최근 여러 종류의 초나노 스케일 물질을 합성했다. 합성한 물질은 총 $n$개이고, 각 물질에는 1부터 $n$까지 번호가 붙어 있다. 물질 $i$의 중량은 $w_i$이고, 각 물질은 하나씩만 존재한다.

곧 열리는 세계적인 학회인 "불안정한 물질 박람회"에 이 물질 중 일부를 특수 용기에 담아 가져가려고 하는데, 불안정한 물질이라 제약이 하나 있다. 각 물질 $i$는 특정한 다른 물질과 함께 특수 용기에 담기면 불안정한 특성 때문에 폭발한다. 과학자 X는 여러 번의 실험 끝에 각 물질 $i$가 이런 식으로 반응하는 상대가 오직 하나, 물질 $Q_i$뿐이라는 사실을 알아냈다.

이 정보가 주어졌을 때 과학자 X는 폭발을 일으키지 않는 물질의 조합을 골라 특수 용기에 담아 가려고 한다.

예를 들어 물질을 3개 합성했고 각 물질의 중량이 $w_1 = 3$, $w_2 = 5$, $w_3 = 1$이라 하자. 각 물질과 반응하는 상대 물질의 번호가 $Q_1 = 2$, $Q_2 = 1$, $Q_3 = 2$라 하자.

즉, 1번 물질은 2번 물질과 함께 있으면 반응해 폭발하고, 2번 물질도 1번 물질과 함께 있으면 불안정해져 폭발한다. 마지막으로 3번 물질은 2번 물질과 함께 있으면 폭발한다.

이 경우 1번과 3번 물질은 함께 두어도 안전하고, 중량의 합은 4이다. 하지만 2번 물질 하나만 가져가면 중량 합이 5이므로, 2번 물질만 가져가는 것이 최선이다.

과학자 X는 폭발을 일으키지 않는 물질 조합 중에서 중량의 최댓값을 구하려고 한다. 이 값을 구해보자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 물질의 종류 수 $n$이 주어진다. 다음 $n$개 줄에는 $w_i$와 $Q_i$가 한 줄에 하나씩, 1번 물질부터 순서대로 주어진다.

각 테스트 케이스마다 과학자 X가 가져갈 수 있는 불안정한 물질 조합 중에서 중량의 최댓값을 한 줄에 하나씩 출력한다.

• $1 \le T \le 10$
• $2 \le n \le 100{,}000$
• $1 \le w_i \le 1{,}000{,}000$
• $1 \le Q_i \le n$
• $Q_i \ne i$

중량의 합이 $2^{31}-1$을 넘을 수 있다.