Description

You are given an array $fx$. For each $i(1<=i<=n)$ , we use a point $(i,fx[i])$ in $XoY$ coordinate plane to described it. You are asked to answer $m$ queries, in each query there will be a rectangle and you need to count how many different y-cooordinate (of the points mentioned above) in the queried rectangle.

Format

Input

The first line contains an integer $T(1<=T<=5)$ representing the number of test cases. For each test case , there are two integers $n,m(1<=n<=100000,1<=m<=100000)$ in the first line. Then one line contains $n$ integers $fx[i](0<=fx[i]<=100000)$ Each of the next $m$ lines contain four integers $x0,y0,x1,y1(1<=x0<=x1<=n,0<=y0<=y1<=100000)$ which means matrix's lower-leftmost cell is $(x0,y0)$ and upper-rightest cell is $(x1,y1)$.

Output

For each test case print a single integer in a new line.

Samples

1
4 2
1 0 3 1
1 0 4 3
1 0 4 2

3
2