from math import gcd for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) pref, suf = [0]*n, [0]*n for i in range(n): pref[i] = a[i] suf[n-1-i] = a[n-1-i] if i > 0: pref[i] = gcd(pref[i], pref[i-1]) suf[n-1-i] = gcd(suf[n-1-i], suf[n-i]) if pref[n-1] > 1: print(n) continue ans = 0 for i in range(n): p, s = 0, 0 if i > 0: p = pref[i-1] if i+1 < n: s = suf[i+1] if gcd(p, s) > 1: ans += 1 print(ans)