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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys

sys.setrecursionlimit(int(1e5))


def lcs(w1, w2):
    m, n = len(w1), len(w2)
    dp = tuple([[0] * (n + 1) for _ in range(m + 1)])
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def lcs_recursive(w1, w2, m, n):
    if m == 0 or n == 0:
        return 0
    elif w1[m - 1] == w2[n - 1]:
        return 1 + lcs_recursive(w1, w2, m - 1, n - 1)
    else:
        return max(
            lcs_recursive(w1, w2, m, n - 1), lcs_recursive(w1, w2, m - 1, n))


def solve():
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num

    for pair in zip(word_list[::2], word_list[1::2]):
        cw1, cw2 = map(lambda x: x.strip(), pair)
        # print(lcs(cw1, cw2))
        print(lcs_recursive(cw1, cw2, len(cw1), len(cw2)))

    return None


if __name__ == '__main__':
    solve()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

S = input()
cnt = 0

# O(N^2)は不可。
# 010がある時、01と10を取り除くパターンを作る？
s = S
while True:
    c1 = s.count("01")
    c2 = s.count("10")
    if c1 == 0 and c2 == 0:
        break
    elif c1 >= c2:
        s = s.replace("01", "")
        cnt += c1*2
    else:
        s = s.replace("10", "")
        cnt += c2*2

print(cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-

S = input()

# 最終出力は1のみか0のみとなるはず
# つまり、0と1の個数をカウントし、その差分から答えが求められる

c0 = S.count("0")
c1 = S.count("1")

fin = abs(c0-c1)    # 最後に残る0か1の個数
res = len(S) - fin

print(res)
### BUGGY CODE ###

mod = 10**9 + 7
  
N = int(input())
A = [int(i)%mod for i in input().split()][:N]

WA = [sum(A[:n+1])%mod for n in range(N)]

total = 0
for i in range(N-1):
    total += (A[i]%mod) * ((WA[N-1]-WA[i])%mod)

print(total%mod)

### FIXED CODE ###

mod = 10**9 + 7
  
N = int(input())
A = [int(i)%mod for i in input().split()][:N]

wa = sum(A)

total = 0
for n in range(N-1):
    wa -= A[n]

    total += A[n] * wa
    total %= mod

print(total)
### BUGGY CODE ###

n = int(input())
h_lst = list(map(int, input().split()))
cnt = 0
res = 0
left = 0
for i, h1 in enumerate(h_lst):
  left = h1
  while i <= len(h_lst)-2 and left >= h_lst[i+1]:
    cnt+=1
    left = h_lst[i+1]
    i+=1
  res = max(res, cnt)
  cnt = 0
print(res)

### FIXED CODE ###

n = int(input())
h_lst = list(map(int, input().split()))
cnt = 0
res = 0
for i, left in enumerate(h_lst):
  if i <= len(h_lst)-2 and left >= h_lst[i+1]:
    cnt +=1
  else:
    res = max(res, cnt)
    cnt = 0
print(res)
### BUGGY CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 15

count = 0
for x in range(k+1):
    if x == s:
        count = count + 1
        break
    for y in range(k+1):
        if s == x + y:
            count = count + 1
            break
        for z in range(k+1):
            if s <= k + x + y:
                count = count + 1
                break
print(count)


### FIXED CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 14

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z <= k and 0 <= z:
            count += 1
print(count)
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = list(input())

ans = 999999
for i in range(n):
    left = Counter(s[:i])
    right = Counter(s[i+1:])
    ans = min(ans, left['W'] + right['E'])
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = list(input())
num_w = 0
num_e = Counter(s[1:])['E']
ans = num_e
for i in range(1, n):
    if s[i-1] == 'W':
        num_w += 1
    if s[i] == 'E':
        num_e -= 1
    ans = min(ans, num_w + num_e)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())

l = [2 ** 31 - 1] * n

while q:
    op, s, t = map(int, input().split())
    if op:
        print(min(l[s:t + 1]))
    else:
        l[s] = t
    q -= 1

### FIXED CODE ###

class SegTreeMin:
    SENTINEL = (1 << 31) - 1
    output = []

    def __init__(self, n):
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.SENTINEL] * (n2 << 1)

    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, s, t):
        self.output.append(self._get_min(s, t + 1, 1, 0, self.n2))

    def _get_min(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.SENTINEL
        if a <= l and r <= b:
            return self.tree[k]
        m = (l + r) // 2
        k <<= 1
        return min(
            self._get_min(a, b, k, l, m),
            self._get_min(a, b, k + 1, m, r))

    def print(self):
        print('\n'.join(map(str, self.output)))


n, q = map(int, input().split())
st = SegTreeMin(n)
fs = [st.update, st.get_min]
for c, x, y in (map(int, input().split()) for _ in range(q)):
    fs[c](x, y)
st.print()
### BUGGY CODE ###

N,M=map(int,input().split())
a=[]
b=[]
e=[]
f=[]
g=0
for i in range(M):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
for j in range(M):
    if b[j]!=N:
        if a[j]!=1:
            pass
        else:
            e.append(b[j])
    else:
        f.append(a[j])
if (len(e)==0) or (len(f)==0):
    print('IMPOSSIBLE')
else:
    for l in range(len(e)):
      if e[l] in f:
        g += 1
        break
      else:
        pass
    if g>0:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
island=[[] for i in range(N)]
for j in range(M):
    c,d=map(int,input().split())
    island[d-1].append(c)
    island[c-1].append(d)
f = 0
for k in range(N):
    if 1 in island[k]:
        if N in island[k]:
            f += 1
            break
        else:
            pass
    else:
        pass
if f>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

s = input()
K = int(input())
substrings = {s[i:j]:0 for i in range(len(s)) for j in range(i+1, len(s)+1)}
print(sorted(substrings)[K-1])


### FIXED CODE ###

s = input()
K = int(input())
substrings = {s[i:j]:0 for i in range(len(s)) for j in range(i+1, min(i+1+K, len(s)+1))}
print(sorted(substrings)[K-1])
### BUGGY CODE ###

from functools import reduce
MOD = 10**9 + 7


def calc_2(n):
    ans = 1
    for i in range(n):
        ans *= 2
        ans %= MOD
    return ans - 1


def cmb(N, A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


n, a, b = map(int, input().split())
a %= MOD
b %= MOD


print((calc_2(n) - cmb(n, a) - cmb(n, b)) % MOD)

### FIXED CODE ###

from functools import reduce
MOD = 10**9 + 7


def cmb(N, A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


n, a, b = map(int, input().split())
a %= MOD
b %= MOD


print((pow(2, n, MOD) - 1 - cmb(n, a) - cmb(n, b)) % MOD)
### BUGGY CODE ###

n=int(input())
s=input()
num=[]
for i in range(1000):
    p=str(i)
    while len(p)<3:
        p="0"+p
    num.append(p)
ans=0
for k in range(len(num)):
    q=0
    for i in range(len(s)):
        if q==3:
            break
        elif num[k][q]==s[i]:
            q+=1
    if q==3:
        ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
num=[]
for i in range(1000):
    p=str(i)
    while len(p)<3:
        p="".join(["0",p])
    num.append(p)
ans=0
for k in range(len(num)):
    q=0
    for i in range(len(s)):
        if q==3:
            break
        elif num[k][q]==s[i]:
            q+=1
    if q==3:
        ans+=1
print(ans)
### BUGGY CODE ###

class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
N,K,L=map(int,input().split())       
uf1=Unionfind(N)
uf2=Unionfind(N)
for i in range(K):
  p,q=map(int,input().split())
  uf1.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
ans=[1]*N
for i in range(N):
  for j in range(i):
    if uf1.find(i)==uf1.find(j) and uf2.find(i)==uf2.find(j):
      ans[i]+=1
      ans[j]+=1
ans=list(map(str,ans))
print(" ".join(ans))        

### FIXED CODE ###

from collections import defaultdict
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
N,K,L=map(int,input().split())       
uf1=Unionfind(N)
uf2=Unionfind(N)
for i in range(K):
  p,q=map(int,input().split())
  uf1.unite(p-1,q-1)
for j in range(L):
  r,s=map(int,input().split())
  uf2.unite(r-1,s-1)
d=defaultdict(int)
ans=[0]*N
for i in range(N):
  d[(uf1.find(i),uf2.find(i))]+=1
for i in range(N):
  ans[i]=d[(uf1.find(i),uf2.find(i))]
print(" ".join(map(str,ans)))
### BUGGY CODE ###

import sys

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, S, T = map(int, next(sys.stdin).split())
U = []
V = []
A = []
B = []
for _ in range(M):
    u, v, a, b = map(int, next(sys.stdin).split())
    U.append(u)
    V.append(v)
    A.append(a)
    B.append(b)
graph_yen = coo_matrix((A, (U, V)), shape=(N + 1, N + 1))
graph_snuke = coo_matrix((B, (U, V)), shape=(N + 1, N + 1))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = dijkstra(graph_yen.tocsr(), indices=S, directed=False, unweighted=False)
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = dijkstra(graph_snuke.tocsr(), indices=T, directed=False, unweighted=False)

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))


### FIXED CODE ###

import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')


def dijkstra(graph, start):
    """
    :param list of (list of (int, int)) graph:
    :param int start:
    :return:
    """
    dist = [INF for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


N, M, S, T = list(map(int, input().split()))
graph_yen = [[] for _ in range(N + 1)]
graph_snuuk = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph_yen[u].append((v, a))
    graph_yen[v].append((u, a))
    graph_snuuk[u].append((v, b))
    graph_snuuk[v].append((u, b))

# yen_mins[i]: S から i まで行くときの最小金額
yen_mins = np.array(dijkstra(graph_yen, start=S))
# snuke_mins[i]: T から i まで行くときの最小金額
snuke_mins = np.array(dijkstra(graph_snuuk, start=T))

# totals[i]: i で両替して S から T まで行くときの最大金額
totals = 10 ** 15 - (yen_mins + snuke_mins)[1:]
# 後ろから累積最大値とる
for a in np.maximum.accumulate(totals[::-1])[::-1]:
    print(int(a))
### BUGGY CODE ###

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

n = 1
for i in A_list:
  if 0 in A_list:
    print(0)
    break
  n = n * i
  if n > 1000000000000000000:
    print(-1)
    break
else:
  print(n)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.sort(reverse=True)
n = 1
for i in A_list:
  if A_list[-1] == 0:
    print(0)
    break
  n = n * i
  if n > 1000000000000000000:
    print(-1)
    break
else:
  print(n)
### BUGGY CODE ###

n = int(input())
list_a = list(map(int, input().split()))
list_b = list(map(int, input().split()))
list_c = list(map(int, input().split()))
count = 0
for c in list_c:
    for b in [b for b in list_b if b < c]:
        count += len([a for a in list_a if a < b])
print(count)


### FIXED CODE ###

n = int(input())
list_a = list(map(int, input().split()))
list_b = list(map(int, input().split()))
list_c = list(map(int, input().split()))
list_a.sort()
list_b.sort()
list_c.sort()
list_a.append(10**10)
list_b.append(10**10)
list_c.append(10**10)

list_memo = []
i = 0
j = 0
k = 0
start = 0
list_ans = []
a_count = 0
while k < n:
    if list_c[k] == min(list_a[i], list_b[j], list_c[k]):
        list_memo.append(0)
        list_memo[-1] = sum(list_memo[start:-1])
        list_ans.append(list_memo[-1])
        start = len(list_memo) - 1
        k += 1
    elif list_b[j] == min(list_a[i], list_b[j], list_c[k]):
        list_memo.append(a_count)
        j += 1
    else:
        list_memo.append(0)
        a_count += 1
        i += 1
print(sum(list_ans))
### BUGGY CODE ###

N,Q=map(int,input().split()) 
S=str(input())
for _ in range(Q): 
    x,y = map(int, input().split()) 
    s=S[x-1:y]
    n=s.count('AC')
    print(n)
    

### FIXED CODE ###

N,Q=map(int,input().split()) 
S=input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

x = int(input())
done=False
l=6300
for a in range(-l,l+1):
  for b in range(-l,l+1):
    if(not done and a**5-b**5==x):
      print(a,b)
      done=True

### FIXED CODE ###


x = int(input())
for a in range(-300,301):
  if(a<0):
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
  else:
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())
han=0
kot=0
i=0
if B-1>=N:
    print(math.floor(A*N/B)-A*math.floor(N/B))
    i=1
else:
    for a in range(B-1,N,2*B):
        if han<(math.floor(A*a/B)-A*math.floor(a/B)):
            han=(math.floor(A*a/B)-A*math.floor(a/B))
            kot=a

if i==0:
    print(han)

### FIXED CODE ###

import math
A,B,N=map(int,input().split())
han=0
kot=0
i=0
if B==1:
    print(0)
    exit()
if B-1>=N:
    print(math.floor(A*N/B)-A*math.floor(N/B))
    i=1
else:
    for a in range(B-1,N,B):
        if han<(math.floor(A*a/B)-A*math.floor(a/B)):
            han=(math.floor(A*a/B)-A*math.floor(a/B))
            kot=a

if i==0:
    print(han)
### BUGGY CODE ###

n, k = list(map(int, input().split()))

next = n
while (next >= 0 or n <= next): 
  n = next 
  n = abs(n-k)
 
a, b = list(map(int, input().split()))

n = max(a, b)
k = min(a, b)
prev = k


while (k <= prev and k != 0):
    prev = k
    a = int(n/k)
    b = n % k
    n = max(a, b)
    k = min(a, b)
    # print(a, b, prev, n, k)

print(prev)

### FIXED CODE ###

N, K = list(map(int, input().split()))
x = N % K
print(min(x, K-x))
### BUGGY CODE ###

n, m = map(int, input().split())
query = []
result =  [[] for i in range(n)]
for i in range(m):
    qList = list(map(int, input().split()))
    query.append(qList)
    result[qList[0]-1].append(qList[1])

for i in result:
    i.sort()

for city in query:
    rank = result[city[0]-1].index(city[1])+1
    resultStr = "{}{}".format(str(city[0]).zfill(6), str(rank).zfill(6))
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

N = int(input())
S = list(str(input()))
from collections import Counter
from functools import lru_cache

@lru_cache(maxsize=1000)
def solve(idx, lis, dis):
    if len(lis)==1:
        i = lis[0]
        c = Counter(S[idx:])
        if len(S)>dis:
            if S[dis]==i:
                return c[i]-1
            else:
                return c[i]
        else:
            return c[i]
    elif len(lis)==2:
        ans = 0
        p, q = lis
        for i, j in enumerate(S[idx:]):
            if j==p:
                ans += solve(i+idx, (q,), i*2+idx)
            elif j==q:
                ans += solve(i+idx, (p,), i*2+idx)
        return ans
    else:
        ans = 0
        p, q, r = lis
        for i, j in enumerate(S):
            if j==p:
                ans += solve(i, (q, r), i)
            elif j==q:
                ans += solve(i, (p, r), i) 
            elif j==r:
                ans += solve(i, (p, q), i) 
        return ans

print(solve(0, ('R', 'G', 'B'), 0))

### FIXED CODE ###

N = int(input())
S = list(str(input()))
from collections import Counter

c = Counter(S)
ans = c['B']*c['G']*c['R']
for i in range(N-1):
    for j in range(i, N):
        if S[i]==S[j]:
            continue
        elif i+(j-i)*2>N-1:
            break
        s = S[i+(j-i)*2]
        if s!=S[i] and s!=S[j]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def lcm(a, b):
    return a*b//math.gcd(a, b)


def main():
    N = ii()
    A = list(mi())

    l = 1
    g = A[0]
    k = 1

    for i in range(N):
        l = lcm(l, A[i])
        g = math.gcd(g, A[i])
        k *= A[i]

    if l == k:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, math
from functools import lru_cache
import numpy as np
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def sieve(n):
    res = [i for i in range(n)]

    i = 2
    while i*i < n:
        if res[i] < i:
            i += 1
            continue
        j = i*i
        while j < n:
            if res[j] == j:
                res[j] = i
            j += i
        i += 1

    return res

def factor(n, min_factor):
    res = set()
    while n > 1:
        res.add(min_factor[n])
        n //= min_factor[n]

    return res

def main():
    N = ii()
    A = np.array(list(mi()))

    m = max(A)
    s = sieve(m+1)
    d = defaultdict(bool)
    
    g = np.gcd.reduce(A)
    if g > 1:
        print('not coprime')
        return

    for a in A:
        f = factor(a, s)
        for v in f:
            if d[v]:
                print('setwise coprime')
                return
            d[v] = True

    print('pairwise coprime')



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

n, m, Q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(Q)]
for i in pq:
  p = i[0]
  q = i[1]
  ans = 0
  for j in lr:
    l = j[0]
    r = j[1]
    if p <= l and r <= q:
      ans += 1
  print(ans)

### FIXED CODE ###

def getSumRange(L, R):
    ans = sum[R][R] - sum[R][L - 1] - sum[L - 1][R] + sum[L - 1][L - 1]
    return ans

n, m, Q = map(int, input().split())
L = [0] * m
R = [0] * m
for i in range(m):
    L[i], R[i] = map(int, input().split())
p = [0] * Q
q = [0] * Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())

sum = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
    sum[L[i]][R[i]] += 1
for i in range(n + 1):
    for j in range(n + 1):
        sum[i][j] += sum[i - 1][j]
        sum[i][j] += sum[i][j - 1]
        sum[i][j] -= sum[i - 1][j - 1]

for i in range(Q):
    ans = getSumRange(p[i], q[i])
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
mod = 10**9+7
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        t = a[i]*a[j]
        if t > mod:
            t%=mod
        s += t
        if s > mod:
            s%=mod
print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
k = 0
b = [0]*len(a)
ans = 0
for i in range(len(a)-1, 0, -1):
    k += a[i]
    k %= mod
    b[i] = k
for i in range(len(a)-1):
    ans += a[i] * b[i+1]
    ans %= mod

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

w = []
v = []

n, W = map(int, input().split())

for i in range(n):
    v1, v2 = map(int, input().split())
    w.append(v1)
    v.append(v2)


def knap(i, j):
    res = 0

    if i == n:
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    return res

print(knap(0, W))

### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    w[i], v[i] = map(int, input().split())

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])