Anup has N boxes. He painted them.

He wants to pick W adjacent boxes and give it to Suraj on his birthday. He wants all the W boxes he gifts to be of same colour. Anup repaints some of the boxes, and asks how many ways are there to gift W boxes to Suraj. Can you please help him out?

Input

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a two integers N denoting the number of boxes and W denoting the number of adjacent boxes that he wants to gift Suraj. The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the initial colours of the boxes.
• Third line of each test case contains a single integer Q, denoting the number of times Anup repainted a box. Q lines follow, each containing two integers Pos_i and Col_i meaning that Pos^th box was repainted with colour Col.

Output

• After each repainting query, output the number of ways Anup can gift Suraj W adjacent boxes of the same colour.

Constraints

• 1 = T = 10
• 1 = W, Pos = N
• 1 = A_i, Col = 10⁹
• For 30 points : 1 = Q = 10³, 1 = N = 10⁴
• For 70 points : 1 = Q = 10⁴, 1 = N = 10⁵

Example

Input: 1 4 2 1 1 1 1 3 1 1 1 2 2 2 Output: 3 2 2

Explanation

After the first repaint the boxes are coloured (1,1,1,1), which means 3 ways to choose 2 adjacent boxes of the same colour.
After the second repaint the boxes are coloured (2,1,1,1), which means 2 ways to select 2 adjacent boxes of the same colour.
After the third repaint thee boxes are coloured (2,2,1,1), which means 2 ways to select 2 adjacent boxes of the same colour.