# Practice on Toph

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

## A Unique Array

An array is called “**unique**” if it has no consecutive element with same value(A[i] != A[i-1]).

Given a unique array A of N integer and q queries. Each query will contain 2 integer x,y which updates the value of index x to y (A[x] = y). After each query, if the array is not unique, delete some elements from A to make it unique. Output the maximum size of A which is unique.

### Input

Input starts with an integer T, denoting the number of test cases. The next line contains two integers N, q . The next line contains N space separated integers forming the array A.

The next q lines will contain a query which is in the form x y.

Constraints:

- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10
^{5} - 1 ≤ q ≤ 10
^{5} - 0 ≤ x < Size of Array A
- 1 ≤ y ≤ 10
^{9}

### Output

For each test case, print the case number in a single line. Then for each query you have to print a line containing the Output the maximum size of A which is unique.

### Samples

Input | Output |
---|---|

2 5 3 1 2 3 4 5 0 2 3 3 2 3 1 1 10 0 4 | Case 1: 4 4 2 Case 2: 1 |

For testcase 1

A = [1,2,3,4,5] , After the first operation A = [2,2,3,4,5],

To make it unique, we remove the first element from A making A = [2,3,4,5]

After second operation, A = [2,3,4,3] , It is unique, so no delete operation neededAfter third opeation, A = [2,3,3,3], The largest unique array A = [2,3]

Login to submit