IA is a girl who loves to sing.

With IOI 2018 approaching, IA has decided to write a song for the contestants to express her best wishes. The song consists of $n$ notes, where the pitch of the $i$-th note is $h_i$. IA's vocal range is $A$, meaning she can only sing notes with integer pitches from $1$ to $A$. Therefore, $1 \le h_i \le A$.

Before writing the song, IA needs to determine its structure, so she has written down $Q$ constraints. The $i$-th constraint is: the maximum pitch of the notes with indices between $l_i$ and $r_i$ (inclusive) must be $m_i$. After determining the structure, she can start writing the song. However, she wants to know how many possible songs satisfy all her constraints. Since she heard you are going to IOI in 9 months, she hopes you can help her calculate this value.

Input

The input is read from standard input.

The first line contains an integer $T$ ($T \le 20$), representing the number of test cases.

Each test case starts with a line containing three positive integers $n, Q, A$. The following $Q$ lines each contain three integers $l_i, r_i, m_i$, representing a constraint. It is guaranteed that $1 \le l_i \le r_i \le n$ and $1 \le m_i \le A$.

Output

The output is written to standard output.

The output for each test case should be a single line representing the number of possible songs. Since this number can be very large, output the answer modulo $998244353$.

Examples

Input 1

1
3 2 3
1 2 3
2 3 2

Output 1

3

Note 1

The three possible songs are: $(3,1,2), (3,2,1), (3,2,2)$.

Input 2

2
4 2 4
1 2 3
2 3 4
7 3 74
3 6 56
2 5 56
3 7 70

Output 2

20
160326468

Subtasks