B"Given an array a of length n . Let's construct a square matrix b of size n x n , in which the i -th row contains the array a cyclically shifted to the right by (i - 1) . For example, for the array a = [3, 4, 5] , the obtained matrix is b = begin{bmatrix} 3 & 4 & 5 5 & 3 & 4 4 & 5 & 3 end{bmatrix} Let's construct the following graph: Your task is to calculate the number of connected components ^{ dagger} in the obtained graph. ^{ dagger} A connected component of a graph is a set of vertices in which any vertex is reachable from any other via edges, and adding any other vertex to the set violates this rule. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= q t <= q 10^5 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two integers n and k ( 2 <= n <= 10^6 , 2 <= k <= 2 cdot 10^6 ) -- the length of the array and the parameter k . The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= 10^6 ) -- the elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 10^6 . For each test case, output a single integer -- the number of connected components in the obtained graph. In the first test case, the matrix b is given in the statement. The first connected component contains the vertices (1, 1) , (2, 2) , and (3, 3) . The second connected component contains the vertices (1, 2) , (2, 3) , and (3, 1) . The third connected component contains the vertices (1, 3) , (2, 1) , and (3, 2) . Thus, the graph has 3 connected components. In the second test case, the following matrix is obtained: b = begin{bmatrix} 3 & 4 & 9 9 & 3 & 4 4 & 9 & 3 end{bmatrix} The first conn"...