F. Interval removal
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ with length $$$n$$$.

To make an array beautiful, you must make it as short as possible. What you can do is choose a pair of adjacent elements, provided they are different. After you delete the pair, there may be a new pair that becomes adjacent. e.g. If you delete $$$a_2$$$ and $$$a_3(a_2 \neq a_3)$$$, $$$a_1$$$ and $$$a_4$$$ will become adjacent. After the removals, the minimum length of the array can be achieved is the beauty of the original array.

For example, the beauty of the array $$$[1, 1, 2, 2]$$$ is $$$0$$$, as you can delete element in position $$$2$$$ and $$$3$$$, and the array becomes $$$[1, 2]$$$, then you can make it empty.

However, this could be too easy, so you are also given $$$q$$$ queries. Each query consists of two integers $$$(l,r)$$$, denotes that you need output the beauty of array $$$[a_l,a_{l+1},\dots,a_{r-1},a_r]$$$.

Input

The first line contains an integer $$$T(1 \le T \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

For each test case, the first line consists of a single integer $$$n(1 \le n \le 10^5)$$$ — the length of the array.

The next line consists of $$$n$$$ integers $$$a_i(1 \le a_i \le n)$$$ — the array $$$a$$$.

The next line contains an integer $$$q(1 \le q \le 10^5)$$$ — the number of queries.

The following $$$q$$$ line each consists of two integers $$$l, r(1 \le l \le r \le n)$$$ — the interval that is being queried.

It is guaranteed that $$$\sum n \le 10^5$$$ and $$$\sum q \le 10^5$$$ for all test cases.

Output

For each query, output a single integer in a line — the beauty of the interval.

Example
Input
1
4
1 1 2 2
4
1 4
1 3
1 1
1 2
Output
0
1
1
2
Note

Note that we are only doing the query for the beauty, we don't remove any elements in fact.

For the first sample,

$$$l=1,r=4$$$, The whole array can be removed as described above.

$$$l=1,r=3$$$, The queried array is $$$[1, 1, 2]$$$. You can remove elements in position $$$2$$$ and $$$3$$$ and the array becomes $$$[1]$$$.

$$$l=1,r=2$$$, The queried array is $$$[1, 1]$$$. You can not do any removal.