Unstable Substances

Scientist X has recently succeeded in synthesizing several kinds of ultra-nanoscale substances. There are $n$ substances in total, numbered 1 through $n$. Substance $i$ has weight $w_i$, and exactly one of each substance exists.

Scientist X wants to take some of these substances to the upcoming international conference "Unstable Substances Expo" in a special container, but there is one constraint because the substances are unstable. When substance $i$ is placed in the special container together with a particular other substance, it explodes due to its unstable nature. After many experiments, Scientist X found that each substance $i$ reacts this way with only one other substance, $Q_i$.

Given this information, Scientist X wants to choose a set of substances that does not cause an explosion and take them in the special container.

For example, suppose three substances were synthesized with weights $w_1 = 3$, $w_2 = 5$, $w_3 = 1$. Let the numbers of the substances they react with be $Q_1 = 2$, $Q_2 = 1$, $Q_3 = 2$.

That is, substance 1 reacts and explodes when it is together with substance 2, substance 2 becomes unstable and explodes when it is together with substance 1, and substance 3 explodes when it is together with substance 2.

In this case substances 1 and 3 are safe together and their total weight is 4. However, taking substance 2 alone gives a total weight of 5, so taking only substance 2 is optimal.

Scientist X wants to find the maximum total weight among sets of substances that do not cause an explosion. Find this value.

The first line gives the number of test cases $T$.

The first line of each test case gives the number of substances $n$. The following $n$ lines give $w_i$ and $Q_i$, one per line, in order starting from substance 1.

For each test case, print the maximum total weight among the sets of unstable substances Scientist X can take, one per line.

• $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$

The sum of weights can exceed $2^{31}-1$.