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

lngN, lngC = map(int, input().split())

##  lstD[x][y]
##  C×C
##  x -> y に塗り替えたときの違和感
##  x, y: 0 ... lngC - 1
##  x == y: 0
##  x != y: 1 から 1000 の値を取る
lstD = []
for i in range(lngC):
    lstD.append(list(map(int, input().split())))
##  lstC[i][j]
##  N×N
##  マス(i, j)の初期色
##  1 から C までの値を取る
lstC = []
for i in range(lngN):
    lstC.append(list(map(int, input().split())))
##  lstDSum[r][c]
##  剰余 r のグループを 色 c で塗るときの違和感の和
##  r: 0, 1, 2
##  c: 1 ... lngC
lstDSum = dict()
for r in range(3):
    lstDSum[r] = dict()
    for c in range(1, lngC + 1):
        lstDSum[r][c] = 0##違和感の初期値

for i in range(lngN):
    for j in range(lngN):
        for c in range(1, lngC + 1):
            ##　剰余
            ##　配列は 0 オリジンで, グリッドは 1 オリジンなので,
            ##　配列の座標 i, j から グリッドの座標に変換するために, i, j に 1 足した（意味はない）
            r = ((i + 1) + (j + 1)) % 3
            oriC = lstC[i][j]##初期色
            ##　lstD[初期色][塗り替えた後の色] で 色は, 0 ... lngC - 1までの値を取る
            ##　oriC, cは共に 1 ... lngC までの値を取るので, 1 減らす必要がある
            lstDSum[r][c] += lstD[oriC - 1][c - 1]            

ans = float('inf')
for i in range(1, lngC + 1):
    for j in range(1, lngC + 1):
        if (i != j):
            for k in range(1, lngC + 1):
                if (i != k) and (j != k):
                    ans = min(ans, lstDSum[0][i] + lstDSum[1][j] + lstDSum[2][k])
print(ans)

##グリッドのマス(i, j)とすると,
##(i + j) % 3 の値によって, マスは 3 グループに分かれる (0, 1, 2)

##各グループの色分けの仕方は, itertools.permutations(c, 3) 通り
##内訳は次の通り
    ##(0)色 1 から C までの C 通りに色分け
    ##(1)色 1 から C までの (C - 1) 通りに色分け ((0) 分を除外)
    ##(2)色 1 から C までの (C - 2) 通りに色分け ((0, 1) 分を除外)

##各グループについて
##色 1 から C までの C 通りに色分けしたときの違和感の和を配列化
##lstDSum[グループ番号][色]
    ##グループ番号: 0, 1, 2
    ##色: 1 から C まで

##for 文で, 各グループを塗る色を全探索
##(グループ番号, 色) = (0, i), (1, j), (2, k)とするときの違和感の和
##lstDSum[0][i] + lstDSum[1][j] + lstDSum[2][k]
##これの最小値を取ればよい


### FIXED CODE ###

n, c = map(int, input().split())
arrD = list(list(map(int, input().split())) for i in range(c))
arrC = list(list(map(int, input().split())) for i in range(n))

##剰余r=0,1,2で、
    ##色の出現数を確認する -> いずれかの色に統一する
        ##どの色に統一するか全パターンを実施して、違和感を算出
##和を取る

arrCCnt = []
for r in range(3):
    d = dict()
    for i in range(1, c + 1):
        d[i] = 0
    arrCCnt += [d]

ret = 1000 * 500 * 500
for r in range(3):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if (i + j) % 3 == r:
                arrCCnt[r][arrC[i - 1][j - 1]] += 1##色の出現数を確認

##print(arrCCnt)
for c0 in range(1, c + 1):
    for c1 in range(1, c + 1):
        for c2 in range(1, c + 1):
            if c0 != c1 and c1 != c2 and c2 != c0:
                buf = 0
                ##print(c0,c1,c2)
                for i0 in range(1, c + 1):
                    ##print(i0)
                    buf += arrD[i0 - 1][c0 - 1] * arrCCnt[0][i0]##数
                for i1 in range(1, c + 1):
                    buf += arrD[i1 - 1][c1 - 1] * arrCCnt[1][i1]##数
                for i2 in range(1, c + 1):
                    buf += arrD[i2 - 1][c2 - 1] * arrCCnt[2][i2]##数
                ret = min(ret, buf)
print(ret)
### BUGGY CODE ###

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


# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0 for i in range(N)]
    ans_cnt = 0
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            cons ^= ans[j-1]
        if A[i-1] != cons:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
        if A[i-1] != cons:
            ans[i-1] = 1
            ans_cnt += 1
            ans_str = ans_str + str(i) + " "
            continue
            
    print(ans_cnt)
    print(ans_str)
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)
### BUGGY CODE ###

import random
from collections import defaultdict


# CPythonの文字列検索アルゴリズム (BM法) を利用
# http://effbot.org/zone/stringlib.htm


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid-mid+1
        for i in range(0, m):
            if S[i:i+mid] in S[i+mid:]:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

### FIXED CODE ###

import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [S[:i].count('AC') for i in range(1, len(S) + 1)]
# print('cnt', cnt)
for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0]
for i in range(2, len(S) + 1):
    if S[i - 2:i] == 'AC':
        v = cnt[-1] + 1
    else:
        v = cnt[-1]
    cnt.append(v)

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

n, m = map(int, input().split())
groups = [x for x in range(n)]
count = [0]*n

def UnionFind(x):
    while x != groups[x]:
        x = groups[x]
    return x

for _ in range(m):
    x, y = map(int, input().split())
    x, y = UnionFind(x-1), UnionFind(y-1)
    if x != y:
        groups[y] = x

for i in range(n):
    count[UnionFind(i)] += 1
print(max(count))


### FIXED CODE ###

n, m = map(int, input().split())
groups = [x for x in range(n)]
count = [0]*n

def UnionFind(x):
    a = x
    while a != groups[a]:
        a = groups[a]
    groups[x] = a
    return a

for _ in range(m):
    x, y = map(int, input().split())
    x, y = UnionFind(x-1), UnionFind(y-1)
    if x != y:
        groups[y] = x
    
for i in range(n):
    count[UnionFind(i)] += 1
print(max(count))
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
c=[0]*(n+1)
ans=0
for i in range(0,n):
  c[d[i]]+=1

if d[0]!=0 or c[0]!=1:
  print(0)
  
else:
  for j in range(1,n):
    if c[j]==0 and c[j+1]==0:
      ans+=0
    else:
      if j==1:
        ans+=1
      else:
        ans*=c[j-1]**c[j]
  print(ans%998244353)  
    
  



### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
x=max(d)
li=[0]*(x+1)
for i in range(n):
    li[d[i]]+=1
if d[0]!=0 or li[0]!=1:
    print(0) 
else:
    ans=1
    for i in range(2,len(li)):
        ans*=pow(li[i-1],li[i],998244353)   
    print(ans%998244353)
### BUGGY CODE ###

from collections import Counter

N, M = list(map(int, input().split()))
range_dict = Counter()
for _ in range(M):
    l, r = list(map(int, input().split()))
    for i in range(l, r+1):
        range_dict[i] += 1

print(len([v for k, v in range_dict.most_common() if v==M]))


### FIXED CODE ###

from collections import Counter

N, M = list(map(int, input().split()))
max_l = 1
min_r = N
for _ in range(M):
    l, r = list(map(int, input().split()))
    if max_l < l:
        max_l = l
    if min_r > r:
        min_r = r

print(min_r - max_l + 1 if min_r - max_l >= 0 else 0)
### BUGGY CODE ###

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであるに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # TODO verify both in directed and non-directed
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d


import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for i in range(M)]
graph = WarshallFloyd(N)
for a, b, c in ABC:
    graph.add(a-1, b-1, c)

d = graph.WarshallFloyd_search()
ans = float('inf')
for each in itertools.permutations(r):
    cur = 0
    for i in range(R - 1):
        cur += d[each[i] - 1][each[i + 1] - 1]
    ans = min(ans, cur)

print(ans)

### FIXED CODE ###

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであるに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # TODO verify both in directed and non-directed
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d


import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
graph = WarshallFloyd(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)

d = graph.WarshallFloyd_search()
ans = float('inf')
for each in itertools.permutations(r):
    cur = 0
    for i in range(R - 1):
        cur += d[each[i] - 1][each[i + 1] - 1]
    ans = min(ans, cur)

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

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

ps = [ list(input().split()) for _ in range(m) ]

ac_list = []
wa_count_list = [0]*n
wa_count = 0
ac_count = 0
for i in range(m):
    q = int(ps[i][0])
    if q in ac_list:
        pass
    else:
        if ps[i][1] == "AC":
            ac_count += 1
            ac_list.append(int(ps[i][0]))
            wa_count += wa_count_list[q-1]
        else:
            wa_count_list[q-1] += 1

print(ac_count,wa_count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ps = [ list(input().split()) for _ in range(m) ]

ac_count_list = [0]*n
wa_count_list = [0]*n
wa_count = 0

for i in range(m):
    q = int(ps[i][0])
    if ps[i][1] == "AC":
        if ac_count_list[q-1] == 0:
            ac_count_list[q-1] = 1
            wa_count += wa_count_list[q-1]
        else:
            pass
    else:
        if ac_count_list[q-1]==0:
            wa_count_list[q-1] += 1

print(sum(ac_count_list),wa_count)
### BUGGY CODE ###

def q1():
    _, A, B, C, D = [int(x) - 1 for x in input().split(' ')]
    S = input()
    if "##" in S[A:D + 1]:
        return False
    if C < D:
        return True
    for b in range(B, D + 1):
        if S[b] == '#':
            continue
        s = S[:b] + '#' + S[b + 1:]
        if not "##" in s[A: C + 1]:
            return True
    return False

print('Yes' if q1() else 'No')

### FIXED CODE ###

def q1():
    _, A, B, C, D = [int(x) - 1 for x in input().split(' ')]
    S = input()
    if "##" in S[A:D + 1]:
        return False
    if C < D:
        return True
    for b in range(B, D + 1):
        if S[b] == '#':
            continue
        if (S[b - 1] != "#" and S[b + 1] != "#"):
            return True
    return False

print('Yes' if q1() else 'No')
### BUGGY CODE ###

N = int(input())
A = map(int,input().split())
def kake(a):
  res=1
  for i in a:
    res*=i
  if res > 10**18:
    return -1
  else:
    return res
print(kake(A))

### FIXED CODE ###

N = int(input())
A = map(int,input().split())
def kake(a):
  res=1
  for i in sorted(a):
    res*=i
    if res > 10**18:
      return -1
  else:
    return res
print(kake(A))
### BUGGY CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


def update(i, x, seg):
    i = len(a) + i - 1
    seg[i] = x
    while i > 0:
        i = math.floor((i-1) / 2)  # 上のノード
        # seg[i] = min(seg[2*i + 1], seg[2*i + 2])
        seg[i] = fractions.gcd(seg[2*i + 1], seg[2*i + 2])
    # 数列の1要素を変更可能＞消去で良い＞1要素を0に置換しても良い
    # 1要素を0にした時のリスト全体の最大公約数を今回は返す
    return seg[0]


n, a = II(), LI()
# 最大公約数を求める。gcd(0, x) = 0なので各要素を0で初期化する
segtree = [0] * (2*n -1)
maxi = 0
# node n, parent floor((n-1)/2), chile 2*n + 1 2*n + 2
for i in range(n):
    update(i, a[i], segtree)

for i in range(n):
    tmp = copy.copy(segtree)
    maxi = max(maxi, update(i, 0, tmp))

print(maxi)



### FIXED CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n, a = II(), LI()
left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    left[i] = fractions.gcd(left[i-1], a[i-1])

for i in range(n-1, -1, -1):
    right[i] = fractions.gcd(right[i+1], a[i]) 

# print(left)
# print(right)

maxi = -INF

for i in range(n):
    maxi = max(maxi, fractions.gcd(left[i],right[i+1]))

print(maxi)
### BUGGY CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None


def count_from_K(D, N, K):
    d_from_k = [-1] * (N + 1)
    d_from_k[K] = 0

    current_positions = [(K, 0)]
    reached = [False] * (N + 1)
    reached[K] = True
    while len(current_positions) != 0:
        new_current_positions = []
        for current_position, current_distance in current_positions:
            for node_num, distance_from_current_position in enumerate(
                    D[current_position]):
                if distance_from_current_position != -1 and not reached[node_num]:
                    d_from_k[
                        node_num] = current_distance + distance_from_current_position
                    new_current_positions.append(
                        (node_num,
                         current_distance + distance_from_current_position))
                    reached[node_num] = True

        current_positions = new_current_positions[:]

    return d_from_k


def main():
    N = int(input())
    D = [[-1] * (N + 1) for _ in range(N + 1)]

    for i in range(N - 1):
        a, b, c = li_input()
        D[a][b] = c
        D[b][a] = c

    Q, K = li_input()

    # Kから各頂点までの長さをWFSで求める
    d_from_k = count_from_K(D, N, K)

    for i in range(Q):
        x, y = li_input()
        print(d_from_k[x] + d_from_k[y])


main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
D = None
D_dfs_d = None


def dfs_d(v, pre, dist):
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def main():
    global D
    global D_dfs_d

    N = int(input())
    D_dfs_d = [-1] * (N + 1)
    D = [[] for _ in range(N + 1)]

    for i in range(N - 1):
        a, b, c = li_input()
        D[a].append((b, c))
        D[b].append((a, c))

    Q, K = li_input()

    # Kから各頂点までの長さをWFSで求める
    dfs_d(K, -1, 0)

    for i in range(Q):
        x, y = li_input()
        print(D_dfs_d[x] + D_dfs_d[y])


main()
### BUGGY CODE ###

n = int(input())
ll = [int(w) for w in input().split()]
ll.sort(reverse=True)

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if ll[i] < (ll[j] + ll[k]):
                ans += 1
            else:
                break


print(ans)


### FIXED CODE ###

import bisect

n = int(input())
ll = [int(w) for w in input().split()]
ll.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(ll, ll[i] + ll[j]) - (j + 1)

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

n = int(input())
s = input()
min_c = 9999999

for i in range(n):
   if i == 0:
      cnt = s.count("E")
      if s[0] == "E":
         cnt = cnt - 1
   if i == n -1:
      cnt = s.count("W")
      if s[n-1] == "W":
         cnt -= 1
   else: 
      a = s[:i]
      b = s[i+1:]
      a_cnt = a.count("W")
      b_cnt = b.count("E")
      cnt = a_cnt + b_cnt
   min_c = min(min_c, cnt)

print(min_c)

### FIXED CODE ###

def solve():
    n = int(input())
    s = input()

    cnt = [s[1:n].count("E")]

    for i in range(1, n):
        cnt.append(cnt[i-1] - int(s[i] is "E") + int(s[i-1] is "W"))

    print(min(cnt))

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

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num = int(stdin.readline())

    c = [range(1001) for _ in xrange(1001)]

    for _ in xrange(num):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()

        m = len(x)
        n = len(y)

        for i in xrange(m+1):
            row = c[i]
            for j in xrange(n+1):
                row[j] = 0

        cim1 = c[0]
        for i, xi in enumerate(x, start=1):
            ci = c[i]
            for j, yj in enumerate(y, start=1):
                if xi == yj:
                    ci[j] = cim1[j-1] + 1
                elif cim1[j] >= ci[j-1]:
                    ci[j] = cim1[j]
                else:
                    ci[j] = ci[j-1]
            cim1 = ci

        print(ci[j])


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num = int(stdin.readline())

    for _ in xrange(num):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()

        n = len(y) + 1

        cim1 = [0] * n
        for i, xi in enumerate(x, start=1):
            ci = [0] * n
            for j, yj in enumerate(y, start=1):
                if xi == yj:
                    ci[j] = cim1[j-1] + 1
                elif cim1[j] >= ci[j-1]:
                    ci[j] = cim1[j]
                else:
                    ci[j] = ci[j-1]
            cim1 = ci

        print(ci[j])


main()