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.

Source: codechef | Difficulty: HARD
Tags: Game theory


Solutions:
import sys
input = sys.stdin.readline
import numpy as np
import math

def solution(N, Q, M, A, queries):
	sol = 0
	lcm_ = A[0]
	minus_ = {}
	plus_ = {}
	for [i, j] in queries:
		lcm_ = lcm_ * (A[i - 1] + A[j - 1]) // math.gcd(lcm_, A[i - 1] + A[j - 1])
		if lcm_ > M:
			break
	if lcm_ < M:
		M = lcm_
	diffs = np.array([0 for _ in range(M + 1)])
	for [i, j] in queries:
		minus_[A[i - 1] + A[j - 1]] = minus_.get(A[i - 1] + A[j - 1], 0) + 1
	for [i, j] in queries:
		plus_[A[i - 1], A[i - 1] + A[j - 1]] = plus_.get((A[i - 1], A[i - 1] + A[j - 1]), 0) + 1
	for (val, count) in minus_.items():
		diffs[val:M + 1:val] -= count
	for ((s, b), count) in plus_.items():
		diffs[s:M + 1:b] += count
	cur = 0
	for diff in diffs[1:]:
		cur += diff
		sol = max(sol, cur)
	print(sol)
T = int(input())
for t in range(T):
	(N, Q, M) = map(int, input().split())
	A = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(Q)]
	solution(N, Q, M, A, queries)


t = int(input())
while t > 0:
	(n, q, m) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	from collections import defaultdict
	d = defaultdict(int)
	dp = defaultdict(int)
	arrr = [0] * (m + 2)
	mmx = 0
	for i in range(q):
		(l, r) = [int(i) for i in input().split()]
		l -= 1
		r -= 1
		dp[l, r] += 1
		mmx = max(mmx, arr[r])
	ans = 0
	for (i, j) in dp.items():
		l = min(i)
		r = max(i)
		x = arr[r]
		y = arr[l]
		xx = arr[l] + 1
		while True:
			if y > m or y > mmx + 1000:
				break
			arrr[y] += j
			if y + x > m:
				break
			arrr[y + x] -= j
			y += x + xx - 1
	for i in range(1, m + 2):
		arrr[i] += arrr[i - 1]
		ans = max(ans, arrr[i])
	print(ans)
	t -= 1