Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = tuple(read().split())


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = set()
    while queue:
        x, y = queue.popleft()
        visited.add((x, y))

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and (new_x, new_y) not in visited:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp

print(answer)


### FIXED CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = [list(input()) for i in range(H)]


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)
### BUGGY CODE ###

import sys
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    for x, y in F:
        if x == 0 and y == 0: tan = "NG"
        elif x == 0: tan = "Inf"
        elif y == 0: tan = 0
        else: tan = Fraction(y, x)

        if tan in D: D[tan] += 1
        else: D[tan] = 1

    ans = 1
    used = set()
    for key in D:
        if key not in used and key != "NG":
            this = D[key]
            used |= {key}
            if key == "Inf":
                op = (0 if 0 not in D else D[0])
                used |= {0}
            elif key == 0: 
                op = (0 if "Inf" not in D else D["Inf"])
                used |= {"Inf"}
            else: 
                ne, de = key.numerator, key.denominator
                op = (0 if Fraction(-de, ne) not in D else D[Fraction(-de, ne)])
                used |= {Fraction(-de, ne)}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    if "NG" in D: ans += D["NG"]
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from math import gcd
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    zero, inf, ng = 0, 0, 0
    for x, y in F:
        if x == 0 and y == 0: ng += 1
        elif x == 0: inf += 1
        elif y == 0: zero += 1
        else: 
            g = gcd(abs(x), abs(y))
            if x < 0:
                y *= -1
                x *= -1
            x //= g
            y //= g
            tan = (y, x)
            if tan in D: D[tan] += 1
            else: D[tan] = 1

    ans = 1
    ans *= (pow(2, zero, mod) + pow(2, inf, mod) - 1) % mod
    ans %= mod
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            y, x = key
            rev = ((-x, y) if y > 0 else (x, -y))
            op = (0 if rev not in D else D[rev])
            used |= {rev}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    ans += ng
    ans %= mod
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n, a = list(map(int, input().split()))
xs = list(map(int, input().split()))

na = n*a
DP = [[0]*(na+1) for i in range(n+1)]
DP[0][0] = 1

for _ in range(n):
    x = xs[_]
    next = [[0]*(na+1) for i in range(n+1)]
    for i in range(n):
        for j in range(na+1):
            # xを使わないとき
            next[i][j] += DP[i][j]
            if j+x <= na:
                next[i+1][j+x] += DP[i][j]
    DP = next

# i枚使ったとき合計がi*aである場合の数
ans = 0
for i in range(1,n+1):
    ans += DP[i][i*a]
print(ans)

### FIXED CODE ###

n, a = list(map(int, input().split()))
xs = list(map(int, input().split()))

na = n*a

DP = [[0]*(na+1) for i in range(n+1)]
DP[0][0] = 1

for _ in range(n):
    x = xs[_]
    next = [[0]*(na+1) for i in range(n+1)]
    for i in range(_+1):
        for j in range(na+1):
            # xを使わないとき
            next[i][j] += DP[i][j]
            if j+x <= na:
                next[i+1][j+x] += DP[i][j]
    DP = next

# i枚使ったとき合計がi*aである場合の数
ans = 0
for i in range(1,n+1):
    ans += DP[i][i*a]
print(ans)
### BUGGY CODE ###

n,k = list(map(int,input().split()))
l = list(map(int,input().split()))
ans = 0
if k in l:
    print("POSSIBLE")
    exit()
if n == 1:
    l[0] == k

la = []
while True:
    for i in range(n):
        x = l[i] - k
        xx = l[i] + k
        if x in l or xx in l :
            ans = 1
            break
        else:
            if x not in la:
                la.append(x)
            if xx not in la:
                la.append(x)
        for j in range(i,n):
            a = abs(l[j] - l[i])
            if a == k:
                ans = 1
                break
            else:
                if a in la:
                    ans = 1
                    break
                if a not in l:
                    l.append(a)
                x = a - k
                xx = a + k
                if x in l or xx in l :
                    ans = 1
                    break
                else:
                    if x not in la:
                        la.append(x)
                    if xx not in la:
                        la.append(x)

    _n = n
    n = len(l)
    if n == _n:
        break

if ans == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n,k = list(map(int,input().split()))
l = list(map(int,input().split()))
m = max(l)
for i in range(1,n):
    l[i] = gcd(max(l[i],l[i-1]),min(l[i],l[i-1]))
if k%l[-1] == 0 and k <= m:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N, M = map(int, input().split())
ans = set(range(1,N+1))
for _ in range(M):
    L, R = map(int, input().split())
    tmp = set(range(L,R+1))
    ans = tmp & ans
print(len(ans))

### FIXED CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
L_max = max(L)
L_min = min(R)

for i in range(N):
    if L_max <= i+1 <= L_min:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
arr = []
count = 0
for i in range(n):
    num = int(input())
    if num not in arr:
        arr.append(num)
        count += 1
    else:
        arr.remove(num)
        count -= 1

print(count)


### FIXED CODE ###

n = int(input())
arr = set()
for i in range(n):
    num = int(input())
    if num in arr:
        arr.remove(num)
    else:
        arr.add(num)
print(len(arr))
### BUGGY CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    visit = [False]*n
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        if visit[j]:
            if a[j] != b[j]:
                print(-1)
                return 0
            visit[j-1] = True
            visit[jj] = True
            continue
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            visit[j-1] = True
            visit[jj] = True
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

import bisect
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
    if all(L % L2 != 0 for L2 in lst1):
        lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)

### FIXED CODE ###

import bisect, math
N = 10**5
Q = int(input())

lst1 = [2]
for L in range(3, N, 2):
  f = 0
  for d in range(3, math.floor(math.sqrt(L))+1, 2):
    if L % d == 0:
      f = 1
      break
  if f == 0:
    lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = map(int, input().split())
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print(b-a)
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
abc = 1
for v in A:
    abc *= v
ans = 0
while abc % 2 == 0:
    ans += 1
    abc//=2
print(ans)


### FIXED CODE ###

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    r = readInts()
    cnt = 0
    for i in range(n):
        while r[i] % 2 == 0:
            cnt += 1
            r[i] //= 2
    print(cnt)



if __name__ == '__main__':
  main()
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
count = 0
for i in l:
  while i % 2 == 0:
    count += 1
    i // 2
print(count)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
count = 0
for i in l:
  while i % 2 == 0:
    count += 1
    i //= 2
print(count)
### BUGGY CODE ###

s = list(input())
sur_list = [0 for i in range(2019)]
sur = 0
ans = 0

s.reverse()

for i in range(len(s)):
    sur_list[sur] += 1
    sur = (int(s[i]) * (10**i) + sur) % 2019
    ans += sur_list[sur]

print(ans)


### FIXED CODE ###

s = list(input())
sur_list = [0 for i in range(2019)]
sur = 0
keta = 1
ans = 0

s.reverse()

for i in range(len(s)):
    keta = (keta*10)%2019
    sur_list[sur] += 1
    sur = (int(s[i]) * keta + sur) % 2019
    ans += sur_list[sur]

print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
if K%2==1:
  print((N//K)**3)
else:
  k=K//2
  ans=0
  for a in range(k,N+1,k):
    for b in range(a,N+1,k):
      for c in range(b,N+1,k):
        if (a+b)%K==0 and (b+c)%K==0 and (c+a)%K==0:
          if a==b==c:
            ans+=1
          elif a==b or b==c or c==a:
            ans+=3
          else:
            ans+=6
  print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
if K%2==1:
  print((N//K)**3)
else:
  k=K//2
  print((N//K)**3+((N-k)//K+1)**3)
### BUGGY CODE ###

import bisect

n,m=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)

for i in range(m):
    a[0]=a[0]//2
    a.sort(reverse=True)
print(sum(a))

### FIXED CODE ###

import numpy as np
import bisect
import heapq

n,m=map(int,input().split())
a=np.array([int(i) for i in input().split()])
a=a*(-1)
a.sort()
a=list(a)

for i in range(m):
    check=-(-heapq.heappop(a)//2)
    heapq.heappush(a,check)
print(sum(a)*(-1))
### BUGGY CODE ###

import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      heapq.heappush(q,(0,i,j))

      
ans = 0
while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

N,Q = map(int, input().split())
s = input()

l_list = []
r_list = []
for q in range(Q):
  l,r = map(int, input().split())
  l_list.append(l)
  r_list.append(r)

for q in range(Q):
  s_q = s[l_list[q]-1:r_list[q]]
  cnt = 0
  
  for i in range(len(s_q)-1):
    if s_q[i] == 'A' and s_q[i+1] == 'C':
      cnt += 1
  
  print(cnt)
  




### FIXED CODE ###

N,Q = map(int,input().split())
s = input()

cnt = 0
n = [0]
for i in range(N-1):
    if s[i]+s[i+1] == 'AC':
        cnt += 1
    n.append(cnt)


for i in range(Q):
    l,r = map(int,input().split())
    print(n[r-1]-n[l-1])
### BUGGY CODE ###


k = int(input())

import math
ans = 0
for i in range(1, k + 1):
  for j in range(1, k + 1):
    for l in range(1, k + 1):
      ans += math.gcd(math.gcd(i, j), l)
print(ans)


### FIXED CODE ###

k = int(input())

import math
ans = 0
ans1 = 0
ans2 = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans1 += math.gcd(i,j)

ans = ans + ans1*3

for i in range(1,k+1):
    for j in range(1,i):
        for l in range(1,j):
            ans2 += math.gcd(math.gcd(i,j),l)

ans += ans2*6
print(ans-sum(list(range(k+1)))*2)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
r, g = 0, 0
rmax = N // R
gmax = N // G

for i in range(rmax + 1):
  for j in range(gmax + 1):
    if (N - i * R - j * G) < 0:
      break
    if (N - i * R - j * G) % B == 0:
      ans += 1
#      print(ans, i, j)
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
r, g = 0, 0
rmax = N // R
gmax = N // G

if R * G * B == 1:
  for i in range(N + 1):
    ans += N + 1 - i
  print(ans)
  exit()

for i in range(rmax + 1):
  for j in range(gmax + 1):
    if (N - i * R - j * G) < 0:
      break
    if (N - i * R - j * G) % B == 0:
      ans += 1
#      print(ans, i, j)
print(ans)
### BUGGY CODE ###

def main():
	s = str(input())
	q = int(input())
	shiji = 1
	rcount = 0
	for i in range(q):
		qu = list(map(str,input().split()))
		if qu[0] != '1':
			if shiji == 1:
				if qu[1] == '1':
					s = qu[2] + s
				else:
					s = s + qu[2]
			else:
				if qu[1] == '2':
					s = qu[2] + s
				else:
					s = s + qu[2]
		else:
			shiji *= -1
			rcount += 1
	if rcount % 2 == 0:
		print(s)
	else:
		print(s[::-1])

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	s = str(input())
	q = int(input())
	shiji = 1
	rcount = 0
	from collections import deque
	s = deque(s)
	for i in range(q):
		qu = list(map(str,input().split()))
		if qu[0] != '1':
			if shiji == 1:
				if qu[1] == '1':
					s.appendleft(qu[2])
				else:
					s.append(qu[2])
			else:
				if qu[1] == '2':
					s.appendleft(qu[2])
				else:
					s.append(qu[2])
		else:
			shiji *= -1
			rcount += 1
	if rcount % 2 == 0:
		print(''.join(map(str,s)))
	else:
		s.reverse()
		print(''.join(map(str,s)))

if __name__ == '__main__':
	main()
### BUGGY CODE ###

n=int(input())

X=list(map(int,input().split()))
Y=[]
for i in range(n):
    Y.append(X[i]-(i+1))


res=10000000000000000
for i in range(n):
    cnt=0
    for j in  range(n):
        cnt+=abs(Y[j]-Y[i])
    if cnt<res:
        res=cnt
    
print(res)

### FIXED CODE ###

n=int(input())

X=list(map(int,input().split()))
Y=[]
for i in range(n):
    Y.append(X[i]-(i+1))
Y.sort()
res_1=0

if n%2==1:
    m=Y[int((n-1)/2)]
    for j in range(n):
        res_1+=abs(Y[j]-m)
else:
    m=(Y[int(n/2)-1]+Y[int(n/2)])//2
    for j in range(n):
        res_1+=abs(Y[j]-m)
        

        
print(res_1)
### BUGGY CODE ###

import itertools
inf=10**5
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
ans=inf
for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in itertools.permutations(r):
    preans=0
    for j in range(R-1):
        preans+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,preans)
print(ans)

### FIXED CODE ###

import itertools
inf=10**8
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
ans=inf
for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in itertools.permutations(r):
    preans=0
    for j in range(R-1):
        preans+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,preans)
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split())) 

ans = 0

for a in range(0, N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            n1, n2, n3 = L[a], L[b], L[c]
            if n1<n2+n3 and n2<n3+n1 and n3<n1+n2:
                ans += 1

print(ans)
exit()
from itertools import permutations, combinations,combinations_with_replacement,product

C = list(combinations(L,3))

ans = 0

for i in C:
    a, b, c = i
    if a<b+c and b<c+a and c<a+b:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
L = sorted(list(map(int, input().split()))) 

ans = 0

import bisect

for a in range(N):
    for b in range(a):
        A=L[a]
        B=L[b]
        c=bisect.bisect_left(L, A+B)
        ans+=c-a-1

print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
import math

input = sys.stdin.readline


# 素因数分解O(√n)

def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    for i in range(N):
        pf = primeFactor(A[i])
        for k in pf.keys():
            primes[k] += 1
    pairs = True
    setp = True
    for k in primes.keys():
        if primes[k] != 1:
            pairs = False
        if primes[k] == N:
            setp = False
            break
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
from collections import defaultdict
import sys
import math

input = sys.stdin.readline

# 素因数分解O(√n)


def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    setp = True
    pairs = True
    if gcd(*A) != 1:
        setp = False
        pairs = False
    else:
        for i in range(N):
            pf = primeFactor(A[i])
            for k in pf.keys():
                primes[k] += 1
                if primes[k] != 1:
                    pairs = False
            if not pairs:
                break
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()
### BUGGY CODE ###

s=list(input())
n=len(s)
i,a=0,0
for i in range(n-2):
  if s[i]+s[i+1]+s[i+2]=="ABC":
    s[i],s[i+1],s[i+2]="B","C","A"
    a+=1
    j=1
    while i-j>-1and s[i-j]=="A":
      s[i-j],s[i-j+1],s[i-j+2]="B","C","A"
      a+=1;j+=1
print(a)

### FIXED CODE ###

s=list(input())
n=len(s)
a=0
b=[]
i=0
def ac(b):
  a=b[::-1]
  t,c=0,0
  for i in range(len(b)):
    if a[i]==0:c+=i-t;t+=1
  return c
while i<n:
  f=True
  if s[i]=="A":b.append(0);f=False
  if i<n-1:
    if s[i]+s[i+1]=="BC":b.append(1);f=False;i+=1
  if f:
    a+=ac(b)
    b=[]
  i+=1
print(a+ac(b))
### BUGGY CODE ###

n=int(input())
aa=0
for i in range(1,n+1):
  if i==n:
    aa+=0
  else:
    aa+=i%(i+1)
print(aa)

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

n = int(input())
s = input()
a = [(list(s)[:i]).count("W") + ((list(s)[i:])).count("E") for i in range(len(s))]
print(min(a))

### FIXED CODE ###

n = int(input())
s = input()
a = [0]*(n+2)
b = [0]*(n+2)
for i in range(n):
    a[i+1] = a[i]
    b[-i-2] = b[-i-1]
    if s[i] == "W":
        a[i+1] += 1
    if s[-i-1] == "E":
        b[-i-2] += 1
b = b[2:n+2]
c = [a[i] + b[i] for i in range((n))]
print(min(c))