We all know that a problem is hard when it requires more than one algorithm in the same moment.

         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]

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

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