Description

计算机似乎生来就是干苦力的，不是吗？统计就是这种苦力中的一种，而如果你运气不好，刚好碰到有很多重复数据的时候，就更加令人感到乏味。那么，你的任务来了。现在，给你一列数 A1, A2, … An 。然后要你回答，对于给定的区间，里面到底有多少个不重复的数。

Input

一个整数 T (T <= 10) ，表示有 T 组测试数据。

每组数据第一行是数 N (1 <= N <= 30000) 。

第二行有 N 个数 A1 A2 … An (0 <= Ai <= 2^31 - 1) 。

第三行是数 Q (1 <= Q <= 100000) 。

接下来 Q 行是 Q 个询问 X Y (1 <= x <= y <= N) 。

Output

对于每个询问，输出一个答案，一个答案占一行。

Sample

Input

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

Output

1
2
3
2
3

Source: ycc