Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Battle of Endor

Limits: 2s, 1.0 GB

After myriad battles and death of million rebel soldiers, it is high time to destroy the imperial army, the Dark Force. Some brave and patriot rebel spies collected information about the defense mechanism of imperial bases. To destroy all imperial bases one must destroy the defense shield first. After hours of debating and arguing, the rebel alliance decided that Han Solo is the best choice to do this task. Afterall, who else could risk his/her life rather than Han!

Setter is busy now!!!

Han Solo and his rebel army took their position in the forest of the moon of Endor. The Endor energy shield generator bunker can be seen from here. There is something that bothers Han Solo’s mind. Yes, it is the formation of the imperial army.

Instead of forming a grid formation they formed a single line. The position of each trooper lies between 1 and n and each position has exactly one trooper. There are several groups of imperial troopers and each group has a uniform of unique color. Moreover, each of the troopers has a newly designed blaster rifle, the F-13D Blaster. This rifle can be dangerous because of its powerful energy beam and long range shooting capability.

There are some limitations though. The rifle must be connected to a power supply. The imperial troopers have a light weight device attached to their uniform which can generate huge amount of power. Different groups have different types of devices. To activate all the power supply devices of a group, at least one pair of troops of that group needs to have distance no more than k between them.

Somehow Han knows this information. To make a perfect plan for destroying the bunker, Han needs to know how many strongest groups are there if we consider the troopers in devices within range [l, r] only. A strongest group is the largest group with active power supply.

As the only programmer of the rebel army it’s your turn to help Han destroying the bunker to deactivate the shield. May the force be with you.

Input

Input starts with a positive integer T (1 ≤ T ≤ 10), denoting the number of test cases. Each test case starts with two positive integers n (1 ≤ n ≤ 104) and k (1 ≤ k ≤ n), denoting the number of troopers and the minimum distance to activate the power supply devices. Following line will have n integers denoting the color of each trooper’s uniform (1 ≤ ci ≤ n). Here, ci is the color of the trooper positioned at i. Next line will have a positive integer q (1 ≤ q ≤ 105), denoting the number of queries. Each of the next q lines will have two positive integer l and r (1 ≤ l ≤ r ≤ n), denoting the range.

Output

For each query output the number of strongest groups in a single line.

Samples

InputOutput
2
5 1
1 1 2 2 1
3
1 1
1 2
2 5
7 2
3 1 2 1 2 3 2
5
2 4
3 5
2 5
1 6
2 7
0
1
1
1
1
2
2
1

Data set is huge (around 10 MB). Please use faster I/O.

Author
Discussion
Submit

Login to submit

Editorial

Login to unlock editorial