#446 Modular Range Counting

Statement

Statement language

You are given a sequence $A$ of length $N$ . Process $Q$ queries of the following form.

i j x y: Count the elements among $A_i,A_{i+1},\cdots,A_j$ whose remainder modulo is .

The input is given in the following format:

$T$ case $_1$ case $_2$

For each test case, print the answer to every query on its own line.

#	Score	Constraints
1	5	$N,Q \leq 2\,000$ , and the sums of $N$ and $Q$ over all test cases do not exceed $2\,000$ each.

Input

Output