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

from collections import Counter
S = input()
P = [0] * (len(S)+1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
S = input()
P = [0] * (len(S)+1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10
    d = d % mod

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)
### BUGGY CODE ###

def main():

    s = input()
    t = input()
    m, n = len(s), len(t)
    dp = [["" for _ in range(n+1)] for _ in range(2)]

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[(i+1)%2][j+1] = dp[i%2][j] + s[i]
            else:
                max_l = 0
                max_cand = ""
                for c in [dp[(i+1)%2][j], dp[i%2][j+1]]:
                    if len(c) > max_l:
                        max_l = len(c)
                        max_cand = c
                dp[(i+1)%2][j+1] = max_cand
    return dp[(i+1)%2][n]


if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():

    s = input()
    t = input()
    m, n = len(s), len(t)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    i, j = m, n
    ans = ""
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
    return ans[::-1]


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

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(x) for x in input().split()]
LL=[L[i]*L[i+j] for i in range(0,N) for j in range(1,N-i)]
print(sorted(LL)[K-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)
### BUGGY CODE ###

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

tmp = 0

for i in range(n-1):
    for j in range(i+1,n):
        tmp += a[i] ^ a[j]

print(tmp % (10**9+7))

### FIXED CODE ###

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

mod = 10**9+7

array = [0] * 60

for i in a:
    for j in range(len(bin(i))-2):
        # print(bin(i),i >> j & 1)
        array[j] += (i >> j) & 1

ans = 0
# print(array)

for i in range(60):
    ans += array[i] * (n-array[i]) * 2**i

print(ans % mod)
### BUGGY CODE ###

N=int(input())
lst=[int(d) for d in str(N)]
L=len(lst)
ans=[[0 for e in range(2)] for f in range(L)]
ans[0][0]=lst[L-1]
ans[0][1]=10-lst[L-1]
for i in range(1,L):
 ans[i][0]=min(ans[i-1][0]+lst[L-1-i],ans[i-1][1]+lst[L-1-i]+1)
 ans[i][1]=min(ans[i-1][0]+10-lst[L-1-i],ans[i-1][1]+10-lst[L-1-i]-1)
print(min(ans[L-1][0],ans[L-1][1]+1))


### FIXED CODE ###

N=input()
L=len(N)
ans=[[0 for e in range(2)] for f in range(L)]
k=int(N[L-1])
ans[0][0]=k
ans[0][1]=10-k
if L>1:
 for i in range(1,L):
  k=int(N[L-1-i])
  ans[i][0]=min(ans[i-1][0]+k,ans[i-1][1]+k+1)
  ans[i][1]=min(ans[i-1][0]+10-k,ans[i-1][1]+10-k-1)
print(min(ans[L-1][0],ans[L-1][1]+1))
### BUGGY CODE ###

import sys


def isp(n):
    a = 1
    for i in range(2, (n + 1) // 2 + 2):
        if not n % i:
            a = 0
            break
    return a


ary = []
for i in sys.stdin:
    ary.append(int(i))

for i in ary:
    if i == 2:
        print(1)
    elif i == 3:
        print(2)
    else:
        s = 2
        for x in range(2, i + 1):
            if isp(x):
                s += 1
        print(s)

### FIXED CODE ###

import sys

f = [1, 0, 0, 0, 1, 0] * (1000000 // 6 + 1)
f = [0, 0, 1, 1] + f[3:-2]

i = 5
while i < 1000:
    if f[i] == 1:
        j = i * i
        while j <= 1000000:
            f[j] = 0
            j += i + i
    i += 2

for n in sys.stdin:
    i = int(n)
    print(sum(f[:i + 1]))
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]

dp = [0]*N
for i in range(N):
  if S[i:i+2]=="AC":
    dp[i+1] = dp[i] +1

for i in range(Q):
  print(sum(dp[lr[i][0]:lr[i][1]]))

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split())) for _ in range(Q)]

dp = [0]*(N+1)
for i in range(N):
  if S[i:i+2]=="AC":
    dp[i+1] = dp[i] +1
  else:
    dp[i+1] = dp[i]

for i in range(Q):
  print(dp[lr[i][1]-1]-dp[lr[i][0]-1])
### BUGGY CODE ###

import sys
import time
s1 = time.time()
*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])

# print(time.time() - s1)
mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        level = 0
        while level < 4:
            dp[1][row][col] = max(dp[1][row][col], dp[level][row - 1][col] + grid[row - 1][col - 1])
            dp[0][row][col] = max(dp[0][row][col], dp[level][row - 1][col])
            level += 1
        level = 1
        while level < 4:
            dp[level][row][col] = max(
                dp[level][row][col],
                dp[level - 1][row][col - 1] + grid[row - 1][col - 1],
                dp[level][row][col - 1]
            )
            mx = max(mx, dp[level][row][col])
            level += 1

# print(time.time() - s1)
print(mx)


### FIXED CODE ###

import sys
import time
s1 = time.time()
*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])

# print(time.time() - s1)
mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        level = 0
        dp[1][row][col] = max(dp[1][row][col], dp[3][row - 1][col] + grid[row - 1][col - 1])
        dp[0][row][col] = max(dp[0][row][col], dp[3][row - 1][col])
        level = 1
        v = grid[row - 1][col - 1]
        while level < 4:
            dp[level][row][col] = max(
                dp[level - 1][row][col],
                dp[level][row][col],
                dp[level][row][col - 1],
                dp[level - 1][row][col - 1] + v,
            )
            mx = max(mx, dp[level][row][col])
            level += 1

# print(time.time() - s1)
print(mx)
### BUGGY CODE ###

import sys
import bisect
input=sys.stdin.readline

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

for _ in range(m):
    val=a.pop()//2
    bisect.insort(a, val)

print(sum(a))


### FIXED CODE ###

import sys
import heapq
import numpy as np
input=sys.stdin.readline

n,m=map(int, input().split())
a=list(map(int, input().split()))
h=[]
for val in a:
    heapq.heappush(h, -val)

for _ in range(m):
    val=(-heapq.heappop(h))//2
    heapq.heappush(h, -val)

print(-sum(h))
### BUGGY CODE ###

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


import math

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(x, y, mod):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)

ll = l[0]
rr = len(a) - 1 - l[1]

for k in range(1, n + 2):
    tmp = comb(n + 1, k, 10 ** 9 + 7)
    # print(tmp)

    if ll + rr >= k - 1:
        dc = comb(ll + rr, k - 1, 10 ** 9 + 7)
    else:
        dc = 0
    print(tmp - dc)


### FIXED CODE ###

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

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
    if len(l) == 2:
        break
d = n - l[1] + l[0]

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

mod = (10 ** 9 + 7)

N1 = n + 2
factorial1 = [1]
for i in range(1, N1):
    factorial1.append(factorial1[i - 1] * i % mod)
inverseFactorial1 = [0] * N1
inverseFactorial1[N1 - 1] = power(factorial1[N1 - 1], mod - 2)
for i in range(N1 - 2, -1, -1):
    inverseFactorial1[i] = inverseFactorial1[i + 1] * (i + 1) % mod
def combi1(x, y):
    return factorial1[x] * inverseFactorial1[y] * inverseFactorial1[x - y] % mod

for k in range(1, n + 2):
    if d >= k - 1:
        print((combi1(n+1, k) - combi1(d, k-1)) % mod)
    else:
        print(combi1(n+1, k))
### BUGGY CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = [start]
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in setmada:
			stock.append((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.append(k)
						settansaku.add(k)
	
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.append(k)
					settansaku.add(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

from collections import Counter


def check(s1, s2, i, j, memo):
    if memo[i] == memo[j] and memo[i] != -1:
        return 1
    elif memo[i] != memo[j] and memo[j] != -1:
        return 0

    if s1 == s2:
        if memo[i] == -1:
            memo[i] = i
            memo[j] = i
        elif memo[j] == -1:
            memo[j] = memo[i]
        return 1

    else:
        return 0


def main():
    N = int(input())

    S = []
    for _ in range(N):
        s = input()
        S.append(Counter(s))

    ans = 0
    memo = [-1 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            if len(S[i]) == len(S[j]):
                ans += check(S[i], S[j], i, j, memo)

    print(ans)


main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
ans_dict = {}

for _ in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    try:
        ans_dict[s] += 1
    except:
        ans_dict[s] = 1

ans = 0
for key in ans_dict:
    if ans_dict[key] >= 2:
        ans += combinations_count(ans_dict[key], 2)
print(ans)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
a = np.array([int(input()) for _ in range(M)])

step0 = 1
step1 = 0 if (1 in a) else 1

ans = [step0, step1]
for i in range(2, N+1):
    if i in a:
        now = 0
    else:
        now = ans[-1] + ans[-2]
    ans.append(now)
print(ans[-1] % 1000000007)

### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
A = [1]*(N+1)
for _ in range(M):
    A[int(input())] = 0

step0 = 1
step1 = A[1]

ans = [step0, step1]
for i in range(2, N+1):
    now = (ans[-1] + ans[-2]) * A[i]
    ans.append(now)
print(ans[-1] % 1000000007)
### BUGGY CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]))
print(dp[n-1])

### FIXED CODE ###

import numpy as np
n, k = map(int,input().split())
H = np.array(input().split(), dtype=np.int64)

INF = 10 ** 9 + 1
dp = np.full(n, INF, dtype=np.int64)
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[max(i - k,0):i] + np.abs(H[max(i - k,0):i] - H[i]))

print(dp[-1])
### BUGGY CODE ###

n = int(input())
x =[int(i) for i in input().split()]
c = n//2 - 1

for i in range(0,n):
    temp = x.copy()
    temp.pop(i)
    temp.sort()
    print(temp[c])
    

### FIXED CODE ###

n = int(input())
x =[int(i) for i in input().split()]
c = n//2 - 1
y = x.copy()
y.sort()

for i in range(0,n):
    if y[c] >= x[i]:
        print(y[c+1])
    else:
        print(y[c])
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    b = a
    while b < ans_len:
        # if is_ans[b] == 0:
        is_ans[b] += 1
        b += a

ans = 0
for a in a_list:
    ans += (is_ans[a] == 1)
print(ans)


### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    is_ans[a] += 1
    if is_ans[a] == 1:
        b = 2*a
        while b < ans_len:
            is_ans[b] += 2
            b += a

ans = 0
for a in a_list:
    # print(a, is_ans[a])
    ans += (is_ans[a] == 1)
print(ans)
### BUGGY CODE ###

def readinput():
    n=int(input())
    s=input()
    s=' '+s
    return n,s

def main(n,s):
    count=0
    all=set(['R','G','B'])
    for i in range(1, n-1):
        l1=s[i]
        for j in range(i+1, n):
            l2=s[j]
            if l1==l2:
                continue
            l3=(all - set([l1,l2])).pop()
            ij=j-i
            sub1=s[j+1:j+ij]
            sub2=s[j+ij+1:]
            count+=sub1.count(l3)
            count+=sub2.count(l3)
    return count

if __name__=='__main__':
    n,s=readinput()
    ans=main(n,s)
    print(ans)
       

### FIXED CODE ###

def readinput():
    n=int(input())
    s=input()
    s=' '+s
    return n,s

def main(n,s):
    count=0
    all=set(['R','G','B'])
    for i in range(1, n-1):
        l1=s[i]
        for j in range(i+1, n):
            l2=s[j]
            if l1==l2:
                continue
            l3=(all - set([l1,l2])).pop()
            ij=j-i
            sub1=s[j+1:j+ij]
            sub2=s[j+ij+1:]
            count+=sub1.count(l3)
            count+=sub2.count(l3)
    return count

def main2(n,s):
    count=0
    nr=s.count('R')
    ng=s.count('G')
    nb=s.count('B')
    all=set(['R','G','B'])
    for i in range(1, n-1):
        l1=s[i]
        for j in range(i+1, n):
            l2=s[j]
            if l1==l2:
                continue
            ij=j-i
            jk=ij
            k=j+jk
            if(k>n):
                break
            l3=s[k]
            if l3==l1 or l3==l2:
                continue
            count+=1
    return nr*ng*nb-count



if __name__=='__main__':
    n,s=readinput()
    ans=main2(n,s)
    print(ans)
### BUGGY CODE ###

import queue
k = int(input())
q = queue.Queue([1,2,3,4,5,6,7,8,9])
qg = q.get
qp = q.put
for _ in range(k-1):
  x = qg()
  if x%10 == 0:
    qp(10*x)
    qp(10*x+1)
  elif x%10 == 0:
    qp(10*x+8)
    qp(10*x+9)
  else:
    i = x%10
    qp(10*x+i-1)
    qp(10*x+i)
    qp(10*x+i+1)
x = qg()
print(x)
    
    
    


### FIXED CODE ###

k = int(input())
x = [1,2,3,4,5,6,7,8,9]
i = 0
xa = x.append
while len(x) < k:
  if x[i]%10 == 0:
    xa(10*x[i])
    xa(10*x[i]+1)
  elif x[i]%10 == 9:
    xa(10*x[i]+8)
    xa(10*x[i]+9)
  else:
    j = x[i]%10
    xa(10*x[i]+j-1)
    xa(10*x[i]+j)
    xa(10*x[i]+j+1)
  i += 1
print(x[k-1])
### BUGGY CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
m = copy.copy(a)

k = 1
s = 0
count = 0


for i in range(n):
    if k in a:
        s = a.index(k)
        a = a[s:]
        k += 1
        count += 1
    else:
        break

if k == 1:
    print(-1)
else:
    print(n-(k-1))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
j=1
for i in range(N):
    if j==A[i]:
        j+=1
 
if j==1:
  print(-1)
else:
  print(N-j+1)
### BUGGY CODE ###

N, M, K = map(int, input().split())

fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % 998244353

def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

result = 0
for i in range(K + 1):
    result += M * mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
print(result)


### FIXED CODE ###

N, M, K = map(int, input().split())

result = 0
n = 1
k = 1
for i in range(K + 1):
    result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
    n *= N - 1 - i
    n %= 998244353
    k *= i + 1
    k %= 998244353
result *= M
result %= 998244353
print(result)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
X = [list(map(int,input().split())) for _ in range(Q)]

L = [0]
for i,s in enumerate(S[1:]):
    if s == 'C' and S[i] == 'A':
        L.append(1)
    else:
        L.append(0)

for x in X:
    print(sum(L[x[0]:x[1]]))


### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
X = [list(map(int,input().split())) for _ in range(Q)]

L = [0]
for i,s in enumerate(S[1:]):
    if s == 'C' and S[i] == 'A':
        L.append(L[i]+1)
    else:
        L.append(L[i])

for x in X:
    print(L[x[1]-1]-L[x[0]-1])
### BUGGY CODE ###

s=list(input())
t=list(input())
n=len(s)
m=len(t)
dp=[['' for i in range(m+1)] for j in range(n+1)]
dps=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            dps[i+1][j+1]=dps[i][j]+1
        else:
            if (dps[i+1][j])>(dps[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
                dps[i+1][j+1]=dps[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
                dps[i+1][j+1]=dps[i][j+1]
print(dp[n][m])


### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())

d = [0]*n
for i in range(1, n+1):
    k = 1
    while i*k <= n:
        d[i*k-1] += 1
        k += 1

ans = 0
for i in range(1, n+1):
    ans += d[i-1]*i
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
  d = n // i
  ans += d*(d+1)//2*i
print(ans)
### BUGGY CODE ###

N = int(input())
pair_list = []

ans = 0

for a in range(1, N+1):
    b = 1
    while (a*b < N):
        ans += 1
        b += 1
    
print(ans)


### FIXED CODE ###

N = int(input())

ans = 0

for a in range(1, N+1):
    if N%a==0:
        b_max = int(N/a)-1
    else:
        b_max = int(N//a)
    
    ans += b_max
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=1000000007
c=0
import itertools
a=list(itertools.combinations(A,2))
for i in range(len(a)):
  c+=(a[i][0]*a[i][1])
  c%=MOD
print(c)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c=0
d=sum(A)
for i in range(0,N-1):
    d-=A[i]
    c+=A[i]*d
    if(c>10**9+7):
        c%=(10**9+7)
print(c)
### BUGGY CODE ###

h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
b = [['.']*w for motsu in range(h)]
b[0][0] = '#'
j = 0
for i in range(h):
  if j < w:
    while i<h and j+1 < w:
      if a[i][j+1] == '#':
        j += 1
        b[i][j] = '#'
        if j == w-1:
          break
  if i+1 < h:
    b[i+1][j] = '#'

if a == b:
  print('Possible')
else:
  print('Impossible')

### FIXED CODE ###

h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
c = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      c += 1

if c == h+w-1:
  print('Possible')
else:
  print('Impossible')