当前没有测试数据。

Problem Description

Qiangqiang and Mengmeng are good friends. One day, they were wandering outside when they suddenly saw a bougainvillea tree ahead. It was the season when bougainvillea flowers were in full bloom, and countless petals were growing from the tree at a visible speed.

Upon closer inspection, the tree is actually a weighted tree. At each moment, a new leaf node grows on the tree, and each node has a cute little fairy. The new leaf node also gets a new fairy at the same time. Fairies are cute but fragile creatures, and each fairy $i$ has a "sensitivity value" $r_i$. Fairies $i$ and $j$ become friends if and only if the distance $dist(i,j)$ between them on the tree satisfies $dist(i,j) \leq r_i + r_j$, where $dist(i,j)$ is the sum of the edge weights along the unique path from node $i$ to node $j$ on the tree.

Qiangqiang and Mengmeng are very curious. After every new leaf node grows, they want to know how many pairs of friends there are in the tree.

We assume that the tree starts empty, and the nodes are numbered starting from 1 according to the order they are added. Since Qiangqiang is very curious, you must immediately tell the number of friend pairs in the tree after each new node is added.

Input Format

The first line contains an integer representing the test case number.

The second line contains a positive integer $n$, which indicates the total number of nodes to be added.

We define the number of friend pairs before adding a new node as $last\_ans$, and its initial value is 0.

The next $n$ lines each contain three non-negative integers $a_i, c_i, r_i$, representing the parent node of node $i$ is $a_i \; \oplus \; (last\_ans \; \bmod \; 10^9)$ (where $\oplus$ denotes the bitwise XOR operation, and it is guaranteed that this operation results in a value between 1 and $i-1$), the edge weight between node $i$ and its parent is $c_i$, and the sensitivity value of the fairy on node $i$ is $r_i$.

Note that for node 1, we have $a_1 = c_1 = 0$, which means node 1 is the root node. For $i > 1$, the parent node number is at least 1.

Output Format

For each of the $n$ lines, output an integer representing the number of friend pairs in the tree after adding the $i$-th node.

Sample Input #1

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

Sample Output #1

0
1
2
4
7

Notes

All data satisfy $1 \leq c_i \leq 10^4$, $a_i \leq 2\times 10^9$, $r_i \leq 10^9$.