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

from fractions import Fraction
N = int(input())
A = []
for _ in range(N):
    # A.append(Fraction(input()))
    A.append(int(float(input())*10**9))
ans=0
for i in range(N):
    for j in range(i+1,N):
        if A[i]*A[j] % 10**18 == 0 :
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
a = [[0 for j in range(19)] for i in range(19)]
ans=0
for _ in range(N):
    A=input()
    if A.find('.') > 0:
        count2 = 10 - len(A) + A.find('.')
        count5 = 10 - len(A) + A.find('.')
    else:
        count2 = 9
        count5 = 9
    tmp = int(A.replace('.', ''))
    while count2 < 18:
        if tmp % 2 == 0:
            count2 += 1
            tmp //= 2
        else:
            break
    while count5 < 18:
        if tmp % 5 == 0:
            count5 += 1
            tmp //= 5
        else:
            break
    for i in range(18-count2,19):
        for j in range(18-count5,19):
            ans += a[i][j]
    a[count2][count5] += 1
print(ans)
### BUGGY CODE ###

# cook your dish here
import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
a.sort()
 
 
c = [0]*n #使ったら1
 
res = 0
 
for i in range(n-1,-1,-1):
    if c[i] == 0:
        b = 1
        while b <= a[i]:
            b = b*2
        w1 = bisect.bisect_left(a,b-a[i])
        w2 = bisect.bisect_right(a,b-a[i])
        if w2 >w1:
            for p in range(w1,w2):
                if c[p] == 0 and i != p:
                    res += 1
                    c[p] = 1
                    c[i] = 1
                    break
                
 
print(res)

### FIXED CODE ###

import bisect
 
N = int(input())
A = [int(a) for a in input().split()]
A = sorted(A)
 
c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - A[i] == A[j]:
                c += 1
                A[j] = A[j] - 0.5
                A[i] = A[i] + 0.5
print(c)
### BUGGY CODE ###

import sys

def f(a,b,c,cur):
    if max(a,b,c)>lim:
        return 0
    if cur==n:
        return 1
    t=(a,b,c,cur)
    if t in memo:
        return memo[t]
    re1=f(a+ms[cur],b,c,cur+1)
    re2=f(a,b+ms[cur],c,cur+1)
    re3=f(a,b,c+ms[cur],cur+1)
    re=re1+re2+re3
    memo[t]=re
    return re

memo={}
n=int(sys.stdin.readline())
ms=[]
for i in range(n):
    ms+=[int(sys.stdin.readline())]
lim=(sum(ms)-1)//2
print(f(ms[0],0,0,1)*3%998244353)

### FIXED CODE ###

import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    # ALL-NG（NG…最大辺が周の半分以上になる）で求める
    # 最大辺を赤として、dp[r] 赤の和がrのパターンを求める
    # 「赤だけ」、「赤と他一色だけ」(両方dp2に含まれる)のパターンは除く必要がある
    # 赤の和が総和の半分以上になるパターンを考えるので、
    # 赤以外の色だけになるパターンは除く必要がない
    # その後、緑、青が最大の辺になる場合も考えて3倍

main()
### BUGGY CODE ###

import queue

def count(S, K):
    c = 0
    q = queue.Queue()
    q.put((S, 0))
    s = []
    while(q.empty() == False):
        x, y = q.get()
        if x < 0:
            break
        if x <= K and y <= K and S-x-y <= K and (x, y) not in s:
            s.append((x, y))
            c += 1
        q.put((x-1, y+1))
        q.put((x-1, y))
    return c

if __name__ == "__main__":
    inp = [int(i) for i in input().split()]
    K = inp[0]
    S = inp[1]
    print(count(S, K))

### FIXED CODE ###

if __name__ == "__main__":
    inp = [int(i) for i in input().split()]
    K = inp[0]
    S = inp[1]
    c = 0
    for x in range(K+1):
        for y in range(K+1):
            z = S - x - y
            if z >= 0 and z <= K:
                c += 1
    print(c)
### BUGGY CODE ###

n,m,k = map(int,input().split())
shelfA = list(map(int,input().split()))
shelfB = list(map(int,input().split()))
prodA = [0]*(n+1)
prodB = [0]*(m+1)
for i in range(1,n+1):
    prodA[i] = prodA[i-1] + shelfA[i-1]
for i in range(1,m+1):
    prodB[i] = prodB[i-1] + shelfB[i-1]
if(n>=m):
    ans = [-1]*(n+1)
    for i in range(n+1):
        for j in range(m+1):
            if(prodA[i]+prodB[j] <= k):
                if(ans[i] < i+j):
                    ans[i] = i+j
            else:
                break
            
else:
    ans = [-1]*(m+1)
    for i in range(m+1):
        for j in range(n+1):
            if(prodB[i]+prodA[j] <= k):
                if(ans[i] < i+j):
                    ans[i] = i+j
            else:
                break

print(max(ans))

### FIXED CODE ###

n,m,k = map(int,input().split())
shelfA = list(map(int,input().split()))
shelfB = list(map(int,input().split()))
prodA = [0]*(n+1)
prodB = [0]*(m+1)
for i in range(1,n+1):
    prodA[i] = prodA[i-1] + shelfA[i-1]
for i in range(1,m+1):
    prodB[i] = prodB[i-1] + shelfB[i-1]

ans = -1
j = m
for i in range(n+1):
    if(prodA[i]>k):
        break
    while(prodB[j] > k - prodA[i]):
        # print(prodB[j],j,k-prodA[i])
        j-=1
    # print(ans)
    ans = max(ans,i+j)



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

n=int(input())
s=input()
if n<=3:
    print(0)
    exit()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                if j-i!=k-j:
                    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
if n<=3:
    print(0)
    exit()
r=set()
g=set()
b=set()
for i,c in enumerate(s):
    if c=='R':
        r.add(i)
    elif c=='G':
        b.add(i)
    else:
        g.add(i)
ans=0
lb=len(b)
for i in r:
    for j in g:
        t1=-1
        if abs(i-j)%2==0:
            t1=min(i,j)+abs(i-j)//2
        t2=max(i,j)+abs(i-j)
        t3=min(i,j)-abs(i-j)
        tc=0
        if t1 in b:
            tc+=1
        if t2 in b:
            tc+=1
        if t3 in b:
            tc+=1
        ans+=max(0,lb-tc)
print(ans)
### BUGGY CODE ###

a,b = map(int, input().split())

t = [1,]
flag = 0

for i in range(1000):
    t.append((i+2)+ t[i])

for j in range(len(t)):
    for k in range(499500):
        if t[j] - k == a and t[j+1] - k == b:
            print(k)
            flag = 1
        if flag == 1:break
    if flag == 1: break

### FIXED CODE ###

a,b = map(int, input().split())

t = [1,]

for i in range(1000):
    t.append((i+2)+ t[i])

for j in range(len(t)):
    if t[j] - a == t[j+1] - b:
        print(t[j] - a)
        break
### BUGGY CODE ###

s = list(input())
ans = [0]*len(s)
t = len(s)
for i in range(t):
    if s[i] == "R":
        x = s[i:].index("L")+i
        if (x-i)%2 == 0:
            ans[x] += 1
        else:
            ans[x-1] += 1
    else:
        x = i-list(reversed(s[:i])).index("R")
        if (i-x)%2 == 0:
            ans[x] += 1
        else:
            ans[x-1] += 1
for i in ans:
    print(i,end = " ")
    

### FIXED CODE ###

s = list(input())
ans = [s[0]]
cnt = 1
if len(s) == 1:
    print(s[0],end = "")
    print(1)
else:
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            cnt += 1
        else:
            ans.append(cnt)
            ans.append(s[i+1])
            cnt = 1
    if s[-1] == s[-2]:
        ans.append(cnt)
    else:
        ans.append(1)
ans2 = [0]*len(s)
sm = 0
for i in range(len(ans)//2):
    sm += ans[2*i+1]
    if ans[i*2] == "L":
        if ans[2*i+1]%2 == 1:
            ans2[sm-ans[i*2+1]] += (ans[2*i+1]+1)//2
            ans2[sm-ans[i*2+1]-1] += (ans[2*i+1]-1)//2
        else:
            ans2[sm-ans[i*2+1]] += (ans[2*i+1])//2
            ans2[sm-ans[i*2+1]-1] += (ans[2*i+1])//2
    else:
        if ans[2*i+1]%2 == 1:
            ans2[sm-1] += (ans[2*i+1]+1)//2
            ans2[sm] += (ans[2*i+1]-1)//2
        else:
            ans2[sm] += (ans[2*i+1])//2
            ans2[sm-1] += (ans[2*i+1])//2
for i in ans2:
    print(i,end = " ")
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 0

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = dp[h][w] + 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = dp[h][w] + 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = dp[h][w] + 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = dp[h][w] + 1
            temp.append([h,w-1])
    ls = temp

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

#ABC-79-B
from functools import lru_cache

n = int(input())

#@lru_cache(maxsize=None)
def lucas(n):
    if n == 1:
        return 2
    elif n == 2:
        return 1
    else:
        return lucas(n-2)+lucas(n-1)
    

print(lucas(n+1))
    

### FIXED CODE ###

#ABC-79-B
from functools import lru_cache

n = int(input())

@lru_cache(maxsize=None)
def lucas(n):
    if n == 1:
        return 2
    elif n == 2:
        return 1
    else:
        return lucas(n-2)+lucas(n-1)
    

print(lucas(n+1))
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
#P = []
#Y = []
for i in range(M):
    p, y = map(int, input().split())
    #P.append(p)
    #Y.append(y)
    L.append([i, p, y])

#L = list(zip(range(M), P, Y))     

Order = [None]*M
P = [p for (i, p, y) in L]

for v in set(P):
    l = filter(lambda x:x[1] == v, L)
    l_ = sorted(l, key = lambda x:x[2])
    
    for n in l_:
        Order[n[0]] = l_.index(n)+1
        
for (p, od) in zip(P, Order):
    print('{0:0>6d}{1:0>6d}'.format(p, od))

### FIXED CODE ###

N, M = map(int, input().split())
L = []
P = [0]*(N+1)
for i in range(M):
    p, y = map(int, input().split())
    L.append([i, p, y, 0])

L = sorted(L, key = lambda x:x[2])

for l in L:
    P[l[1]] += 1
    l[3] = P[l[1]]    
        
for l in sorted(L, key = lambda x:x[0]):
    print('{0:0>6d}{1:0>6d}'.format(l[1], l[3]))
### BUGGY CODE ###

from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
n = 10**6
d={}
pairflag=1
setflag=0
#primes = set(range(2, n+1))
#for i in range(2, int(n**0.5+1)):
#    primes.difference_update(range(i*2, n+1, i))
#primes=list(primes)
#print(len(primes))
buf=[0]*(max(A)+10)
seen=[0]*(max(A)+10)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
for num in range(N):
    m=A[num]
    #print(m)
    for i in range(2, int(sqrt(m)) +1):
        while m%i==0:
            if seen[i]==0:
                buf[i]=1
                m //= i
            else:
                pairflag=0
                break
        if pairflag==0:
            break
    if pairflag==1:
        if m>1:
            if seen[m]==0:
                buf[m]=1
            else:
                pairflag=0
                break
    else:
        break
    #    if pairflag==0:
    #        break
    seen=buf[:]
    #print(m,seen,buf,pairflag)
#print(pairflag)

num=A[0]
for i in range(1,N):
    num=ggcd(num,A[i])
if num==1:
    setflag=1
else:
    setflag=0

if pairflag==1:
    print("pairwise coprime")
elif setflag==1:
    print("setwise coprime")
else:
    print("not coprime")

"""
x=list(set(A))
for i in x:
    for j in range(2*i,10**6+1,i):
        if d.get(j)!=None:
            pairflag=0
            break
    if pairflag==0:
        break
print(pairflag)

"""

### FIXED CODE ###

from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
n = 10**6
d={}
pairflag=1
setflag=0
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
#print(len(primes))
buf=[0]*(max(A)+10)
seen=[0]*(max(A)+10)
for i in range(N):
    if d.get(A[i])==None:
        d[A[i]]=1
    else:
        d[A[i]]=d[A[i]]+1
#print(d)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
for i in primes:
    cnt=0
    for j in range(i,10**6+1,i):
        if d.get(j)!=None:
            cnt=cnt+d[j]
    if cnt>1:
        pairflag=0
        break

num=A[0]
for i in range(1,N):
    num=ggcd(num,A[i])
if num==1:
    setflag=1
else:
    setflag=0

if pairflag==1:
    print("pairwise coprime")
elif setflag==1:
    print("setwise coprime")
else:
    print("not coprime")

"""
x=list(set(A))
for i in x:
    for j in range(2*i,10**6+1,i):
        if d.get(j)!=None:
            pairflag=0
            break
    if pairflag==0:
        break
print(pairflag)

"""
### BUGGY CODE ###

s=input()
l=len(s)

dp=[[0,0,0,0] for i in range(l)]
mod=10**9+7
c=0

for i in range(l):
    if s[i]=="A":
        dp[i][1]=dp[i-1][1]+3**c
        dp[i][2]=dp[i-1][2]
        dp[i][3]=dp[i-1][3]
    elif s[i]=="B":
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]+dp[i-1][1]
        dp[i][3]=dp[i-1][3]
    elif s[i]=="C":
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
        dp[i][3]=dp[i-1][3]+dp[i-1][2]
    else:
        dp[i][1]=dp[i-1][1]*3+3**c
        dp[i][2]=dp[i-1][2]*3+dp[i-1][1]
        dp[i][3]=dp[i-1][3]*3+dp[i-1][2]
        c+=1
    dp[i][1]=dp[i][1]%mod
    dp[i][2]=dp[i][2]%mod
    dp[i][3]=dp[i][3]%mod

print(dp[-1][3])


### FIXED CODE ###

s=input()
l=len(s)
dp=[[0]*4 for i in range(l+1)]
dp[0][0]=1
mod=10**9+7
for i in range(l):
    c = s[i]
    dp[i+1][0]=dp[i][0] 
    dp[i+1][1]=dp[i][1] 
    dp[i+1][2]=dp[i][2] 
    dp[i+1][3]=dp[i][3] 
    if c=="A":
        dp[i+1][1]+=dp[i][0]
    if c=="B":
        dp[i+1][2]=dp[i][2]+dp[i][1] 
    if c=="C":
        dp[i+1][3]=dp[i][3]+dp[i][2]
    if c=="?":
        dp[i+1][0] = (3*dp[i][0])%mod
        dp[i+1][1] = (dp[i][0] + 3*dp[i][1]) % mod
        dp[i+1][2] = (dp[i][1] + 3*dp[i][2]) % mod
        dp[i+1][3] = (dp[i][2] + 3*dp[i][3]) % mod
        

print(dp[-1][3]%mod)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]
# a = [int(input()) for x in range (n)]

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[0]


for x in range(0,mi*2+1,2) :
    # print(x)
    b[0] = x

    for i in range(1,n) :
        b[i] = 2 * a[i-1] - b[i-1]
        # print(b)
        if (b[i] < 0) : 
            break

    else :
        if (b[-1] + b[0] == 2 * a[-1]) :
            break


# s = str(b)
# for i in b :
#     s = s + str(i) + " " 

# print(s)
print(str(b).strip("[]").replace(",",""))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[0]

aa = 0
for i in range(1, n, 2) :
    aa += a[i]
b[0] = sum(a) - 2 * aa

for i in range(1,n) :
    b[i] = 2 * a[i-1] - b[i-1]
print(str(b).strip("[]").replace(",",""))
### BUGGY CODE ###

from scipy.sparse.csgraph import shortest_path, dijkstra


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n = int(input())
dists = []
for i in range(n):
    ds = map(int, input().split())
    for j, c in enumerate(ds):
        if i >= j:
            continue
        dists.append((c, i, j))
dists.sort()

uf = UnionFind(n)
links = [[0] * n for _ in range(n)]
ans = 0

for c, i, j in dists:
    if not uf.find(i, j):
        links[i][j] = c
        links[j][i] = c
        ans += c
        uf.union(i, j)
        continue
    graph = dijkstra(links, directed=False, indices=i)
    if graph[j] < c:
        break
    elif graph[j] > c:
        links[i][j] = c
        links[j][i] = c
        ans += c

graph = dijkstra(links, directed=False)
for c, i, j in dists:
    if graph[i][j] != c:
        print(-1)
        break
else:
    print(ans)


### FIXED CODE ###

def solve(n, tbl):
    ans = 0
    for i, row_i in enumerate(tbl):
        for j in range(i + 1, n):
            row_j = tbl[j]
            ij = row_i[j]
            mind = min((ik + kj for ik, kj in zip(row_i, row_j) if ik and kj), default=float('inf'))
            if ij > mind:
                return -1
            if ij < mind:
                ans += ij
    return ans


n = int(input())
tbl = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, tbl))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    ans = 0
    cnt = [[0]*20 for _ in range(45)]
    for _ in range(n):
        a = list(map(str, input().rstrip().split(".")))
        x = 0
        if len(a) == 1:
            x = int(a[0]) * 10**9
        else:
            x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
        cnt_2, cnt_5 = 0, 0
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(45):
            for j in range(20):
                if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                    ans += cnt[i][j]
        cnt[cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
ans = 0
cnt = [[0]*20 for _ in range(45)]
for _ in range(n):
    a = list(map(str, input().rstrip().split(".")))
    x = 0
    if len(a) == 1:
        x = int(a[0]) * 10**9
    else:
        x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        cnt_2 += 1
        x //= 2
    while x % 5 == 0:
        cnt_5 += 1
        x //= 5
    for i in range(45):
        for j in range(20):
            if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                ans += cnt[i][j]
    cnt[cnt_2][cnt_5] += 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split(' '))
S = input()
ans = 0
ans_list = []
for i in range(Q):
    l, r = map(int, input().split(' '))
    ans_list.append(S[l - 1: r].count('AC') or 0)
[print(ans) for ans in ans_list]


### FIXED CODE ###

# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    if (l - 2 < 0):
        result = cum[r - 2]
    else:
        result = cum[r - 2] - cum[l - 2]
    ans_list.append(result)
[print(ans) for ans in ans_list]
### BUGGY CODE ###

import sys
import numpy as np


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = [(0, 0) for _ in range(m)]
    row = np.zeros(h, dtype=int)
    col = np.zeros(w, dtype=int)
    for i in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target[i] = (hi, wi)
        row[hi] += 1
        col[wi] += 1
    r = row.max()
    ri = [i for i in range(h) if row[i] == r]
    c = 0
    for rii in ri:
        ci = col.copy()
        for y, x in target:
            if y == rii:
                ci[x] -= 1
        c = max(ci.max(), c)
    ans = r + c
    c = col.max()
    ci = [i for i in range(w) if col[i] == c]
    r = 0
    for cii in ci:
        ri = row.copy()
        for y, x in target:
            if x == cii:
                ri[y] -= 1
        r = max(ri.max(), r)
    ans = max(r + c, ans)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = [0] * h
    col = [0] * w
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    row_max = max(row)
    r = [i for i in range(h) if row[i] == row_max]
    col_max = max(col)
    c = [i for i in range(w) if col[i] == col_max]
    for ri in r:
        for ci in c:
            if (ri, ci) not in target:
                print(row_max + col_max)
                return
    print(row_max + col_max - 1)


if __name__ == '__main__':
    main()