Unique Spells in the Forest

In a magical forest, each tree is endowed with a spell represented by an integer. You are given multiple test cases. For each test case, you will have an array of spells corresponding to N trees and Q queries. Each query is defined by two integers L and R representing the range (inclusive, 1-indexed) of trees. Your task is to determine the number of unique spells present in each queried segment.

Mathematically, for an array (A) of size (N) and a query ((L, R)), you are required to compute (|{A_i : L \leq i \leq R}|), where (|S|) denotes the cardinality of the set (S).

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer (T) representing the number of test cases.
  For each test case:
  
  • The first line contains an integer (N), the number of trees in the forest.
    
  • The second line contains (N) space-separated integers, where the (i^{th}) integer represents the spell on the (i^{th}) tree.
    
  • The third line contains an integer (Q), the number of queries.
    
  • Each of the next (Q) lines contains two space-separated integers (L) and (R) indicating a query for the segment from tree (L) to tree (R) (inclusive).

outputFormat

For each query, output the number of unique spells in the specified segment. The answers for all queries across all test cases should be printed in order on separate lines via standard output (stdout).## sample

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

2
3
4