import sys
input = sys.stdin.readline
inf = float('inf')
def getInt():
return int(input())
def getStr():
return input().strip()
def getList(split=True):
s = getStr()
if split:
s = s.split()
return map(int, s)
t = getInt()
N = 20
def solve():
from math import gcd, log2
from functools import reduce
n = getInt()
a = list(getList())
t = [[0] * N for _ in range(n)]
target = reduce(gcd, a)
for i, j in enumerate(a):
t[i][0] = j
for k in range(1, N):
for i in range(n):
t[i][k] = gcd(t[i][k-1], t[(i + (1 << k-1)) % n][k-1])
def get(l, r):
k = int(log2(r-l+1))
return gcd(t[l][k], t[(r-(1 << k)+1) % n][k])
res = 0
j = 0
for i in range(n):
j = max(j, i)
g = get(i, j)
while g != target:
j += 1
g = gcd(g, a[j % n])
res = max(res, j-i)
print(res)
for _ in range(t):
solve()
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5;
const int LOG_MAX = 19;
const int UNIT = 1, NONE = -1;
int gcdOf (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int input[1 + 2 * NMAX]; int n;
int Table[1 + 2 * NMAX][1 + LOG_MAX]; int logOf[1 + 2 * NMAX];
void getTable (int n) {
logOf[1] = 0;
for (int i = 2; i <= 2 * n; i ++)
logOf[i] = logOf[i / 2] + 1;
for (int i = 1; i <= 2 * n; i ++)
Table[i][0] = input[i];
for (int bit = 1; (1 << bit) <= 2 * n; bit ++)
for (int i = 1; i + (1 << bit) - 1 <= 2 * n; i ++)
Table[i][bit] = gcdOf (Table[i][bit - 1], Table[i + (1 << (bit - 1))][bit - 1]);
}
int queryGCD (int i, int j) {
int lg = logOf[j - i + 1];
return gcdOf (Table[i][lg], Table[j - (1 << lg) + 1][lg]);
}
int main()
{
int t; cin >> t;
for (int tc = 1; tc <= t; tc ++) {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> input[i];
for (int i = n + 1; i <= 2 * n; i ++)
input[i] = input[i - n];
int totalGCD = 0;
for (int i = 1; i <= 2 * n; i ++)
totalGCD = gcdOf (totalGCD, input[i]);
for (int i = 1; i <= 2 * n; i ++)
input[i] /= totalGCD;
getTable (n);
int answer = 0;
for (int i = 1; i <= n; i ++) {
int left = 0, right = n, target = NONE;
while (left <= right) {
int mid = left + (right - left) / 2;
if (queryGCD (i, i + mid) == UNIT) {
target = mid;
right = mid - 1;
}
else
left = mid + 1;
}
answer = max (answer, target);
}
cout << answer << "\n";
}
return 0;
}
1671D - Insert a Progression | 1671A - String Building |
1671B - Consecutive Points Segment | 1671C - Dolce Vita |
1669G - Fall Down | 4D - Mysterious Present |
1316B - String Modification | 1204A - BowWow and the Timetable |
508B - Anton and currency you all know | 1672A - Log Chopping |
300A - Array | 48D - Permutations |
677C - Vanya and Label | 1583B - Omkar and Heavenly Tree |
1703C - Cypher | 1511C - Yet Another Card Deck |
1698A - XOR Mixup | 1702E - Split Into Two Sets |
1703B - ICPC Balloons | 1702F - Equate Multisets |
1700A - Optimal Path | 665C - Simple Strings |
1708A - Difference Operations | 1703E - Mirror Grid |
1042A - Benches | 1676B - Equal Candies |
1705B - Mark the Dust Sweeper | 1711A - Perfect Permutation |
1701B - Permutation | 1692A - Marathon |