“Why climb? Because the mountain is there.”

There are $n$ locations on Mount Mustagh, numbered from $1$ to $n$, with location $1$ being the summit. These $n$ locations form a rooted tree structure, where location $1$ is the root, and for $2 \le i \le n$, the parent of location $i$ is $p_i$.

Let $d_i$ be the number of edges from location $i$ to the summit. Formally, $d_1 = 0$, and for $2 \le i \le n$, $d_i = d_{p_i} + 1$.

A climbing path is defined as a scheme starting from any location in $2 \sim n$ and reaching the summit after a number of moves.

A move from location $i$ ($2 \le i \le n$) is defined as one of the following two types:

1. Sprint: Within a given sprint range $[l_i, r_i]$, choose a positive integer $k$ such that $l_i \le k \le r_i$, and move $k$ steps towards the summit, i.e., move to the $k$-th level ancestor of location $i$ in the rooted tree. It is guaranteed that $1 \le l_i \le r_i \le d_i$.
2. Rest: Due to the steep terrain of Mount Mustagh, resting causes one to slide down to one of the child nodes. Formally, choose a $j$ such that $p_j = i$, and move to location $j$. Specifically, if location $i$ is a leaf node of the rooted tree, there exists no $j$ such that $p_j = i$, so one cannot choose to rest in this case.

A climbing sequence corresponding to a climbing path is the sequence formed by the initial location and each location reached after every move. Formally, the climbing sequence corresponding to a climbing path starting from location $x$ is a sequence of locations $a_1 = x, a_2, \dots, a_m = 1$ such that for $1 \le i < m$, $a_{i+1}$ is the $k$-th ancestor of $a_i$ ($l_{a_i} \le k \le r_{a_i}$) or $p_{a_{i+1}} = a_i$.

To ensure that every sprint gets closer to the summit, a legal climbing path must satisfy: for the initial location or any location $i$ reached during the path, any subsequent location $j$ reached by a sprint must satisfy $d_j < d_i - h_i$, where $h_i$ is a given parameter. It is guaranteed that $0 \le h_i < d_i$. Formally, the climbing sequence $a_1, a_2, \dots, a_m$ corresponding to a legal climbing path must satisfy: for all $1 \le i < j \le m$, if $p_{a_j} \neq a_{j-1}$, then $d_{a_j} < d_{a_i} - h_{a_i}$.

For all locations $2 \sim n$, calculate the number of legal climbing paths starting from these locations. Two climbing paths are different if and only if their corresponding climbing sequences are different. Since the answer may be large, you only need to output the result modulo $998,244,353$.

Input

Read the data from the file mountain.in.

This problem contains multiple test cases. The first line contains an integer $c$, representing the test case number. $c = 0$ indicates that this test case is a sample. The second line contains an integer $t$, representing the number of test cases. Following this, the data for each test case is provided. For each test case: The first line contains an integer $n$, representing the number of locations on Mount Mustagh. The next $n-1$ lines, the $(i-1)$-th line ($2 \le i \le n$) contains four integers $p_i, l_i, r_i, h_i$. It is guaranteed that $1 \le p_i < i$, $1 \le l_i \le r_i \le d_i$, and $0 \le h_i < d_i$.

Output

Output to the file mountain.out. For each test case, output a single line containing $n-1$ integers, representing the number of ways to reach the summit from locations $2 \sim n$, respectively, modulo $998,244,353$.

Examples

Input 1

0
3
5
1 1 1 0
2 1 1 0
2 1 2 1
4 2 3 0
6
1 1 1 0
2 1 2 0
3 1 3 2
4 1 4 1
5 1 5 3
6
1 1 1 0
2 1 2 0
2 1 2 0
3 1 2 0
3 2 3 2

Output 1

3 3 2 4
5 9 3 21 6
4 10 5 14 1

Note

Sample 1 contains three test cases. For the first test case, the structure of Mount Mustagh is as follows:

In this test case: $d_1 = 0, d_2 = 1, d_3 = d_4 = 2, d_5 = 3$. There are 2 legal climbing paths starting from 4: 1. Directly choose to sprint to the 2nd-level ancestor of 4, which is 1, reaching the summit. The corresponding climbing sequence is $[4, 1]$. 2. First rest and slide to 5; then sprint from 5 to its 3rd-level ancestor, reaching the summit. The corresponding climbing sequence is $[4, 5, 1]$.

There are 4 legal climbing paths starting from 5: 1. Directly choose to sprint to the 3rd-level ancestor of 5, which is 1, reaching the summit. The corresponding climbing sequence is $[5, 1]$. 2. First sprint to the 2nd-level ancestor of 5, which is 2; then sprint from 2 to its 1st-level ancestor, reaching the summit. The corresponding climbing sequence is $[5, 2, 1]$. 3. First sprint to the 2nd-level ancestor of 5, which is 2; then rest at 2, sliding to 4; then sprint from 4 to its 2nd-level ancestor, reaching the summit. The corresponding climbing sequence is $[5, 2, 4, 1]$. 4. First sprint to the 2nd-level ancestor of 5, which is 2; then rest at 2, sliding to 4; continue to rest, sliding to 5; then sprint from 5 again to its 3rd-level ancestor, reaching the summit. The corresponding climbing sequence is $[5, 2, 4, 5, 1]$.

Input 2

(mountain/mountain2.in)

Output 2

(mountain/mountain2.ans)

Input 3

(mountain/mountain3.in)

Output 3

(mountain/mountain3.ans)

Input 4

(mountain/mountain4.in)

Output 4

(mountain/mountain4.ans)

Input 5

(mountain/mountain5.in)

Output 5

(mountain/mountain5.ans)

Constraints

For all test cases, it is guaranteed that $1 \le t \le 4$, $2 \le n \le 10^5$. For any $2 \le i \le n$, it is guaranteed that $1 \le p_i < i$, $1 \le l_i \le r_i \le d_i$, and $0 \le h_i < d_i$.