Steven has an array of non-negative integers. The -th integer (indexed starting from 0) in the array is .
Steven really likes subintervals of that are xor-even. Formally, a subinterval of is a pair of indices , denoting the elements . The xor-sum of this subinterval is , where xor is the bitwise exclusive or.
A subinterval is xor-even if its xor-sum has an even number of set bits in its binary representation.
Steven would like to make modifications to the array. The -th modification changes the -th (indexed from 0) element to . Steven would like to know, what is the size of the xor-even subinterval of A with the most elements after each modification?
输入格式
The first line of the input gives the number of test cases, . test cases follow.
Each test case starts with a line containing two integers and , denoting the number of elements in Steven's array and the number of modifications, respectively.
The second line contains integers. The -th of them gives indicating the -th integer in Steven's array.
Then, lines follow, describing the modifications. The -th line contains and . The -th modification changes the -th element to , indicating that the -th modification changes the -th (indexed from 0) element to .
输出格式
For each test case, output one line containing Case #x: y_1 y_2 . . . y_Q, where x is the test case number (starting from 1) and y_i is the number of elements in the largest xor-even subinterval of after the -th modification. If there are no xor-even subintervals, then output 0.
After the 1st modification, is . The subinterval has xor-sum . In binary, the xor-sum is , which has an even number of bits, so the subinterval is xor-even. This is the largest subinterval possible, so the answer is .
After the 2nd modification, is . The largest xor-even subinterval is , which has xor-sum . In binary, this is .
After the 3rd modification, is . The largest xor-even subinterval is again, which has xor-sum . In binary, this is .
In Sample Case 2, and . After the 1st modification, is . The largest xor-even subinterval is , which has xor sum . In binary, this is .
