You are given an array A consisting of N integers. You have to process Q queries to this array, the ith query is given as four integer Li, Ri, Xi and Yi, you need to calculate how many subarray(l,r) meet the following three conditions at the same time:
1. Li ≤ l ≤ r ≤ Ri.
2. Xi ≤ r − l + 1 ≤ Yi.
3. There is no repeating integer in the subarray(l, r).
In this problem, subarray(l,r) is defined as non-empty sequence of consecutive elements from Al to Ar inclusively.
The first line contains an integer T, where T is the number of test cases. T test cases follow.For each test case, the first line contains one integer N, where N is the size of array A.The second line contains N integers A1, A2, ..., AN, where Ai is the ith element of array A.The third line contains one integer Q, where Q is the number of queries you have to process.Then Q lines follow, the ith line contains four integers Li, Ri, Xi and Yi denoting ith query.• 1 ≤ T ≤ 10.
• 1 ≤ N, Ai ≤ 105.• 1 ≤ Q ≤ 105.• 1 ≤ Li ≤ Ri ≤ N.• 1 ≤ Xi ≤ Yi ≤ N.
For each test case, output one line containing “Case #x:”, where x is the test case number (starting from
1). The following Q lines, each line output an integer indicating the number of subarrays that meet the
above three conditions.