**Problem Description**

But we still tend to believe bravery can help us overcome difficulties.

The result of this problem will depend on how brave you are.

You have an array a and its’s size equals n.

There are exactly n positive constant number in your array.

Now you are faced with q query which consists of four integer: L1, R1, L2, R2.

Please answer how many different pair(i, j) where L1 <= i <= R1 and L2 <= j <= R2 and a[i] = a[j].

We consider two pair is same if and only if they look the same completely.

For example, (3, 3) is different from (3, 5).

(3, 5) and (3, 5) look the same.

Attention![L1, R1] may intersect with [L2, R2]

**Input**

An integer T on the first line representing there will be T test cases（1 <= T <= 100）

An integer n on the second line representing your array’s size.（1 <= n <= 100）

There are exactly n positive integers ai on the third line separated by space, each represents the ith element.（1 <= ai <= 100）

An integer q on the fourth line representing that there will be q query waiting for you.

Q lines follows, each contains four integer: L1, R1, L2, R2.

1 <= L1 <= R1 <= n

1 <= L2 <= R2 <= n

**Output**

For each query, print an integer respecting your answer in one line.

**Sample Input**

1 5 1 2 3 2 1 4 1 1 5 5 1 5 1 5 1 2 4 5 1 3 3 5

**Sample Output**

1 9 2 3

**Hint**

All legal pair(i, j) of the first query：（1，5）

All legal pair(i, j) of the second query：（1，1），（1，5），（2，2），（2，4），（3，3），（4，2），（4，4），（5，1），（5，5）

All legal pair(i, j) of the third query：（1，5），（2，4）

All legal pair(i, j) of the fifth query：（1，5），（2，4），（3，3）

Someone said : “Inclusion-exclusion principle + Off-line algorithms +Mo’s algorithm，now you are accepted.”

**Source**

2019绍兴联赛