n = int(input())
string = input()
dp = [[0]*2 for x in range(n)]
dp[0][0] = 1 dp[0][1] = float("inf") for x in range(1, n):
    dp[x][0] = dp[x-1][0]+1  midIndex = (x+1)//2   if (x+1)%2==0 and string[:midIndex]==string[midIndex:x+1]:
        dp[x][1] = min(dp[x-1][1]+1, dp[midIndex-1][0]+1) else:
        dp[x][1] = dp[x-1][1]+1 print(min(dp[n-1]))

T = int(input()) for x in range(T):
    n, m, k = list(map(int, input().split()))
    prohibitColorBit = [] #注意ci 1<=ci<=m  for x in range(m):
        line = set(map(lambda x:int(x)-1, input().split()))
        bit = 0  for x in line:
            bit = bit | (1<<x)
        prohibitColorBit.append(bit) #0<=ci<m  dp = [[0]*m for x in range(n)] for x in range(n): for curColor in range(m): if x==0:
                dp[x][curColor] = 1  continue  else: for prevColor in range(m): if 1<<curColor & prohibitColorBit[prevColor]: continue  else:
                        dp[x][curColor] += (dp[x-1][prevColor])
    print(sum(dp[n-1])%(10**9+7))

n = int(input())
ai = list(map(int, input().split()))
bi = list(map(int, input().split()))
dp = [[0]*2*n for x in range(2*n)]
preSum = [0] for x in range(len(ai)):
    curSum = -ai[x] + bi[x]
    curSum += preSum[-1]
    preSum.append(curSum) for x in range(2*n-1, -1, -1): for y in range(2*n): if x==y:
            dp[x][y] = ai[x] elif y<x: continue  else: #dp[x][y]表示干掉x到y需要的最少血量  #dp[x+1][y]  #干掉x, y-1剩下的血量  leftLeft = dp[x][y-1] + preSum[y]-preSum[x]
            rightLeft = dp[x+1][y] + preSum[y+1] - preSum[x+1]
            leftNeed = dp[x][y-1]
            rightNeed = dp[x+1][y] if leftLeft <= ai[y]:
                leftNeed += (ai[y]-leftLeft+1) if rightLeft<= ai[x]:
                rightNeed += (ai[x]-rightLeft+1) #处于同一边  if x<=n-1 and y<=n-1: # print(y)  dp[x][y] = leftNeed continue  if x>=n and y>=n: # print(x)  dp[x][y] = rightNeed continue  if leftNeed<rightNeed: # print(y)  dp[x][y] = leftNeed else: # print(x)  dp[x][y] = rightNeed print(dp[0][2*n-1]) # 3 # 5 6 7 8 9 5 # 8 7 5 6 10 12