Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Array Stabilization (GCD version)

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given an array of positive integers $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ ($$$n \ge 2$$$).

In one step, the array $$$a$$$ is replaced with another array of length $$$n$$$, in which each element is the greatest common divisor (GCD) of two neighboring elements (the element itself and its right neighbor; consider that the right neighbor of the $$$(n - 1)$$$-th element is the $$$0$$$-th element).

Formally speaking, a new array $$$b = [b_0, b_1, \dots, b_{n - 1}]$$$ is being built from array $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ such that $$$b_i$$$ $$$= \gcd(a_i, a_{(i + 1) \mod n})$$$, where $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$x \mod y$$$ is the remainder of $$$x$$$ dividing by $$$y$$$. In one step the array $$$b$$$ is built and then the array $$$a$$$ is replaced with $$$b$$$ (that is, the assignment $$$a$$$ := $$$b$$$ is taking place).

For example, if $$$a = [16, 24, 10, 5]$$$ then $$$b = [\gcd(16, 24)$$$, $$$\gcd(24, 10)$$$, $$$\gcd(10, 5)$$$, $$$\gcd(5, 16)]$$$ $$$= [8, 2, 5, 1]$$$. Thus, after one step the array $$$a = [16, 24, 10, 5]$$$ will be equal to $$$[8, 2, 5, 1]$$$.

For a given array $$$a$$$, find the minimum number of steps after which all values $$$a_i$$$ become equal (that is, $$$a_0 = a_1 = \dots = a_{n - 1}$$$). If the original array $$$a$$$ consists of identical elements then consider the number of steps is equal to $$$0$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case contains two lines. The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — length of the sequence $$$a$$$. The second line contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

Print $$$t$$$ numbers — answers for each test case.

Example

Input

5 4 16 24 10 5 4 42 42 42 42 3 4 6 4 5 1 2 3 4 5 6 9 9 27 9 9 63

Output

3 0 2 1 1

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/21/2021 22:30:15 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|