Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a strictly increasing sequence of positive integers $A_{1}, A_{2}, \ldots, A_{N}$. It is also guaranteed that for each valid $i$, $A_{i}+A_{1} ≥ A_{i+1}$.

Alice and Bob want to play $Q$ independent games using this sequence. Before they play these games, Alice should choose a positive integer $G$ between $1$ and $M$ (inclusive). The rules of each game are as follows:
There is a set $S$ of positive integers representing allowed moves in this game. For each valid $i$, in the $i$-th game, this set is $S = \{A_{L_{i}},A_{L_{i}+1},\ldots,A_{R_{i}}\}$ (in other words, given by a contiguous subsequence of $A$).
The game is played with a single pile. Let's denote the number of objects in this pile by $P$. At the beginning of the game, $P = G$. In other words, Alice and Bob play all the games with the same initial number of objects that Alice chooses.
The players alternate turns; Alice plays first.
In each turn, the current player must choose a positive integer $b$ from the set $S$ such that $b ≤ P$ and remove $b$ objects from the pile, i.e. change $P$ to $P-b$.
When the current player cannot choose any such integer $b$, this player loses this game.

Both players play optimally. You need to find the maximum number of games Alice can win if she chooses $G$ optimally.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $Q$ and $M$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
$Q$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $L_{i}$ and $R_{i}$.

------ Output ------
For each test case, print a single line containing one integer ― the maximum number of games Alice can win.

------ Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N,Q,M ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{8}$ for each valid $i$
$A_{i}+A_{1} ≥ A_{i+1} > A_{i}$ for each valid $i$
$1 ≤ L_{i} ≤ R_{i} ≤ N$ for each valid $i$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$
the sum of $Q$ over all test cases does not exceed $2 \cdot 10^{5}$
the sum of $M$ over all test cases does not exceed $2 \cdot 10^{5}$

------ Subtasks ------
Subtask #1 (5 points):
$N,Q,M ≤ 400$
the sum of $N$ over all test cases does not exceed $400$
the sum of $Q$ over all test cases does not exceed $400$
the sum of $M$ over all test cases does not exceed $400$

Subtask #2 (30 points):
$N,Q,M ≤ 5,000$
the sum of $N$ over all test cases does not exceed $5,000$
the sum of $Q$ over all test cases does not exceed $5,000$
the sum of $M$ over all test cases does not exceed $5,000$

Subtask #3 (65 points): original constraints

----- Sample Input 1 ------
1

3 2 10

2 3 4

1 2

2 3
----- Sample Output 1 ------
2
----- explanation 1 ------
Example case 1: The set of allowed moves in the first game is $S = \{2,3\}$ and in the second game, it is $S = \{3,4\}$. If Alice chooses $G=3$, she can win both games.

见题面

见题面