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

# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, stdin.readline().rstrip().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)



### FIXED CODE ###

# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)
### BUGGY CODE ###

import math
A, B = map(int, input().split())

digits = 0

i = B
mid = A + (B - A) // 2

partSum = B * (B+1) // 2 - A * (A+1) // 2 + A
S = 0
while S != partSum:
	x = i
	while x >= A:
		digits = digits ^ x
		S += x
		if x % 2:
			break
		x //= 2
	i -= 1
	
print(digits)

### FIXED CODE ###

A, B = map(int, input().split())

ones = [0] * 101
def calcones(end, pow):
	start = pow // 2
	if end < pow // 2:
		return 0
	
	n = (end - start + 1) // pow
	n *= pow // 2
	
	if 0 < (end - start + 1) % pow <= pow // 2:
		n += (end - start + 1) % pow
		
	return n

pow = 2
for i in range(1, 101):
	ones[i] = calcones(B, pow) - calcones(A-1, pow)
	pow *= 2
	
# print(ones)
		
ans = 0
pow = 1
for i in range(1, 101):
	ans += (ones[i] % 2) * pow
	pow *= 2
	
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if min(x, y, z) < 0 or z > k:
            continue
        ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    if 0 <= s - x <= k:
        ans += s-x+1
    elif 0 <= s-x-k <= k:
        ans += k - s + x + k + 1
    # print(x, ans)
print(ans)
### BUGGY CODE ###

N =int(input())
s = sorted(sorted(input()) for i in range(N))
cnt = 0
i = 0
while i <= N-1:
    grnm=(s[i+1:]).count(s[i])
    if grnm == 0:
        i+=1
    else:
        cnt += int(grnm*(grnm+1)/2)
        i+=(grnm+1)
print(cnt)

### FIXED CODE ###

import collections

N =int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
cnt = 0
ans =0
for i in set(s):
    cnt = c[i]
    ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

N=int(input())
c=input().replace('W','1').replace('R','0')
c=[int(x) for x in c]
count=0

if sum(c)!=0 and sum(c)!=N:
    while True:
        w=c.index(1)
        r=N-c[::-1].index(0)-1
        if w>r:
            break
        count+=1
        c[w]=0 ; c[r]=1

print(count)

### FIXED CODE ###

N=int(input())
c=input()
count=0

if 'WR' in c:
    x=c.count('R')
    y=c.count('R',0,x)
    count=x-y
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

def rec(i):
    if dp[i] != 0:
        return dp[i]
    res = 0
    if i == 1 or i == 2:
        res = abs(H[i]-H[0])
        dp[i] = res
        return res
    elif i == 0:
        return 0
    else:
        res = min(abs(H[i]-H[i-2])+rec(i-2),abs(H[i]-H[i-1])+rec(i-1))
        dp[i] = res
        return res

rec(n-1)

print(dp[n-1]) 

### FIXED CODE ###

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

for i in range(1,n):
    if i == 1 or i == 2:
        dp[i] = abs(H[i]-H[0])
    else:
        dp[i] = min(abs(H[i]-H[i-2])+dp[i-2],abs(H[i]-H[i-1])+dp[i-1])

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

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
lst = []
for i in range(n-1):
    for j in range(i+1,n):
        lst.append(a[i]*a[j])

lst.sort()
print(lst[k-1])

### FIXED CODE ###

N,K = map(int,input().split())
plst = []
nlst = []
p = 0
z = 0
n = 0
for i in map(int,input().split()):
    if i > 0:
        p += 1
        plst.append(i)
    elif i == 0:
        z += 1
    else:
        n += 1
        nlst.append(i)
plst.sort()
nlst.sort()
zp = (p+n)*z + z*(z-1)//2
np = p*n
if K <= np:
    l = -10**18-1
    r = 0
    while l+1 < r:
        m = (l+r)//2
        total = 0
        idx = 0
        for i in range(p):
            while idx < n:
                if plst[i] * nlst[idx] < m:
                    idx += 1
                else:
                    total += idx
                    break
            else:
                total += idx
        if total < K:
            l = m
        else:
            r = m
    ans = l
elif K <= np+zp:
    ans = 0
else:
    l = 0
    r = 10**18+1
    while l+1 < r:
        m = (l+r)//2
        total = np+zp
        tmp = 0
        idx = 0
        for i in range(p)[::-1]:
            while idx < p:
                if plst[i] * plst[idx] < m:
                    idx += 1
                else:
                    tmp += idx
                    break
            else:
                tmp += idx
            if plst[i] * plst[i] < m: tmp -= 1
        tmp //= 2
        total += tmp
        tmp = 0
        idx = 0 
        for i in range(n):
            while idx < n:
                if nlst[i] * nlst[-idx-1] < m:
                    idx += 1
                else:
                    tmp += idx
                    break
            else:
                tmp += idx
            if nlst[i] * nlst[i] < m: tmp -= 1
        tmp //= 2
        total += tmp
        if total < K:
            l = m      
        else:
            r = m
    ans = l
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nの制約が1000,円の中心を飛び石→dijkstra
sx, sy, gx, gy = lr()
N = ir()
XYR = [[sx, sy, 0]] + [lr() for _ in range(N)] + [[gx, gy, 0]]
graph = [[] for _ in range(N+2)]  # 0がstart,N+1がgoal
for i in range(N+2):
    for j in range(i+1, N+2):
        sp = XYR[i]; ep = XYR[j]
        length = max(0, ((sp[0]-ep[0]) ** 2 + (sp[1]-ep[1]) ** 2) ** .5 - sp[2] - ep[2])
        graph[i].append((j, length))
        graph[j].append((i, length))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+2)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, l in graph[prev]:
            d1 = d + l
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(0)
answer = dist[N+1]
print(answer)
# 46


### FIXED CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nの制約が1000,円の中心を飛び石→dijkstra
sx, sy, gx, gy = lr()
N = ir()
XYR = [[sx, sy, 0]] + [lr() for _ in range(N)] + [[gx, gy, 0]]
graph = [[] for _ in range(N+2)]  # 0がstart,N+1がgoal
for i in range(N+2):
    for j in range(i+1, N+2):
        sp = XYR[i]; ep = XYR[j]
        length = max(0, ((sp[0]-ep[0]) ** 2 + (sp[1]-ep[1]) ** 2) ** .5 - sp[2] - ep[2])
        graph[i].append((j, length))
        graph[j].append((i, length))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+2)
    dist[start] = 0
    que = [(0, start)]
    visited = set()
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, l in graph[prev]:
            if next == prev or next in visited:
                continue
            d1 = d + l
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
        visited.add(prev)
    return dist

dist = dijkstra(0)
answer = dist[N+1]
print(answer)
# 46
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = [input() for h in range(H)]

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    flag = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
                flag = True
                break
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        if flag:
          flag = False
          break        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = [input() for h in range(H)]

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

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

n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num < k:
        tmp = [a] * b
        ls.extend(tmp)
        #ls.sort()
        b_num += b
    else:
        if(a <= max(ls)):
            tmp = [a] * b
            ls.extend(tmp)

ls.sort()
print(ls[k-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = []

for i in range(n):
    a,b = [int(i) for i in input().split()]
    ls.append([a,b])

ls.sort()
for a,b in ls:
    if b >= k:
        print(a)
        break
    else:
        k -= b
### BUGGY CODE ###

K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count = count +1
print(count)

### FIXED CODE ###

K,S=map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count=count+1
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    a += [c] * b
print(sum(sorted(a)[::-1][:n]))

### FIXED CODE ###

n, m = map(int, input().split())
cards = sorted(list(map(int, input().split())))
ope = [list(map(int, input().split())) for i in range(m)]
ope.sort(key=lambda x: x[1], reverse=True)
i, j, k = 0, 0, 0
while i < n and j < m and cards[i] < ope[j][1]:
    cards[i] = ope[j][1]
    i += 1
    k += 1
    if k >= ope[j][0]:
        j += 1
        k = 0
print(sum(cards))
### BUGGY CODE ###

import bisect

D = 10000

X = int(input())

L2 = [i for i in range(-D, D)]
L = [i**5 for i in L2]

idx = bisect.bisect_left(L, X)-1

B = L[:idx]
A = L[idx:]

for a in A:
    for b in B:
        if a - b == X:
            break
    else:
        continue
    break

print(L2[L.index(a)], L2[L.index(b)])


### FIXED CODE ###

import bisect
import math

D = 120

X = int(input())

for a in range(-D, D):
    for b in range(-D-1, D-1):
        if a**5 - b**5 == X:
            break
    else:
        continue
    break

print(a, b)
### BUGGY CODE ###

n,m=map(int,input().split())
for i in range(m,0,-1):
    if m%i==0 and m/n>=i:print(i);break

### FIXED CODE ###

from itertools import *
n,m=map(int,input().split())
M=m
a=[1]
for i in range(2,int(m**.5)+1):
    while m%i==0:
        m//=i
        a+=[i]
if m!=1:a+=[m]
ans=1
for i in range(len(a)):
    for b in combinations_with_replacement(set(a),i):
        c=1
        for j in b:c*=j
        if c>=n and M%c==0:ans=max(ans,M//c)
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
i = 0
while n > i:
    wk = 0
    count = 0
    j = 0
    while wk == count and i >= j:
        if p[j] >= p[i]:
            wk += 1
        count += 1
        j += 1
    if wk == count:
        ans += 1
    i += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
for i in range(n):
    if i == 0:
        ans = 1
        minp = p[i]
    elif minp >= p[i]:
        ans += 1
        minp = min(minp,p[i])
print(ans)
### BUGGY CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]


def judge(n):
    if n == 2 or n == 3:
        return 1
    if n % 2 == 0:
        return 0
    i = 3
    while i < n:
        if n%i == 0:
            return 0
        else:  
            i += 2
    return 1

print(sum(map(judge, ls)))



### FIXED CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]


def judge(n):
    if n == 2 or n == 3:
        return 1
    if n % 2 == 0:
        return 0
    i = 3
    while i <= n/i:
        if n%i == 0:
            return 0
        else:  
            i += 2
    return 1

print(sum(map(judge, ls)))
### BUGGY CODE ###

s = input()

dp3 = 1
dp2 = 0
dp1 = 0
dp0 = 0

for i in reversed(range((len(s)))):
    if s[i] == '?':
        m = 3
    else:
        m = 1

    if s[i] == '?':
        m1 = 3
    else:
        m1 = 1

    if s[i] == '?' or s[i] == 'C':
        m2 = 1
    else:
        m2 = 0

    if s[i] == '?' or s[i] == 'B':
        m3 = 1
    else:
        m3 = 0

    if s[i] == '?' or s[i] == 'A':
        m4 = 1
    else:
        m4 = 0

    t_dp3 = m * dp3
    t_dp2 = m1 * dp2 + m2 * dp3
    t_dp1 = m1 * dp1 + m3 * dp2
    t_dp0 = m1 * dp0 + m4 * dp1
    dp3 = t_dp3
    dp2 = t_dp2
    dp1 = t_dp1
    dp0 = t_dp0

n = 10 ** 9 + 7
ans = dp0 % n
print(ans)

### FIXED CODE ###

s = input()

dp = [[0 for _ in range(4)] for _ in range(len(s) + 1)]
dp[len(s)][3] = 1
n = 10 ** 9 + 7

for i in reversed(range((len(s)))):
    m = 1
    m1 = 1
    m2 = 0
    m3 = 0
    m4 = 0
    if s[i] == '?':
        m = 3
        m1 = 3
        m2 = 1
        m3 = 1
        m4 = 1

    if s[i] == 'C':
        m2 = 1

    if s[i] == 'B':
        m3 = 1

    if s[i] == 'A':
        m4 = 1

    dp[i][3] = (m * dp[i+1][3]) % n
    dp[i][2] = (m1 * dp[i+1][2] + m2 * dp[i+1][3]) % n
    dp[i][1] = (m1 * dp[i+1][1] + m3 * dp[i+1][2]) % n
    dp[i][0] = (m1 * dp[i+1][0] + m4 * dp[i+1][1]) % n

ans = dp[0][0]
print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split(' '))

tmp_list = [i for i in range(A, B + 1)]
tmp_list2 = []

for i in tmp_list[0 : K]:
    tmp_list2.append(i)

for i in tmp_list[len(tmp_list) - K:]:
    if i not in tmp_list2:
        tmp_list2.append(i)

for i in tmp_list2:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split(' '))

if (B - A + 1) / 2 < K:
    for i in range(A, B + 1):
        print(i)
else:
    for i in range(A, A + K):
        print(i)
    for i in range(B - K + 1, B + 1):
        print(i)
### BUGGY CODE ###

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

r = len([i for i in range(n) if s[i] == "R"])
g = len([i for i in range(n) if s[i] == "G"])
b = len([i for i in range(n) if s[i] == "B"])

count = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k >= n:
            break
        if all([s[i] != s[j], s[j] != s[k], s[k] != s[i]]):
            count += 1

print(r * g * b - count)

### FIXED CODE ###

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

r = len([i for i in range(n) if s[i] == "R"])
g = len([i for i in range(n) if s[i] == "G"])
b = len([i for i in range(n) if s[i] == "B"])

count = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            count += 1

print(r * g * b - count)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
for ii in r5000:
  player_in_this_game = set()
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun:
        if m in player_in_this_game or teki - 1 in player_in_this_game:
          #自分または相手に既に試合が組まれている
          pass
        else: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
          a[m].popleft() #自分の予定を消す
          a[teki - 1].popleft() #相手の予定を消す
          player_in_this_game.add(m) #自分を試合中にする
          player_in_this_game.add(teki - 1) #相手を試合中にする
          nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

input()
A = list(map(int, input().split()))

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a % LARGE

print(total % LARGE)


### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

input()
A = list(map(int, input().split()))

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a

print(total % LARGE)
### BUGGY CODE ###

S=input()
L=len(S)
M=2019

k=0
for i in range(L):
    for j in range(i,L):
        if int(S[i:j+1])%M==0:
            k+=1

print(k)


### FIXED CODE ###

S=list(map(int,input()))
L=len(S)
M=2019
d=10

U=[]
for x in range(L):
    if x==0:
        U=[1]
    else:
        U.append((U[-1]*d)%M)
        
T=[0]
for x in range(1,L+1):
    T.append((T[-1]+S[-x]*U[x-1])%M)

D={}
for x in T:
    if x in D:
        D[x]+=1
    else:
        D[x]=1

r=0
for x in D.values():
    r+=(x*(x-1))//2

print(r)
### BUGGY CODE ###

K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D

    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod

print((next_dp[0] + (border == 0) - 1) % mod)


### FIXED CODE ###

K = list(map(int, input()))
D = int(input())

mod = 10 ** 9 + 7

next_dp = [0] * D
border = 0

for current_digit in K:
    dp, next_dp = next_dp, [0] * D
    for current_mod, cnt in enumerate(dp):
        for next_mod in range(current_mod, current_mod + 10):
            next_dp[next_mod % D] += cnt

    for next_mod in range(border, current_digit + border):
        next_dp[next_mod % D] += 1

    border = (border + current_digit) % D

    for i in range(D):
        next_dp[i] %= mod
print((next_dp[0] + (border == 0) - 1) % mod)
### BUGGY CODE ###

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

# 文字数のカウント
cnt=dict()
for a in A:
  if a in cnt.keys():
    cnt[a]+=1
  else:
    cnt[a]=1
    
# 頻出数を探す
cnt_sort = sorted(cnt.items(), key=lambda x:x[1])
cnt_sort.reverse()

# 頻出数3つとその±1の数字を候補とする(最大9つ)
candidates=set()
for i in range(len(cnt)):
  candidates.add(cnt_sort[i][0])
  candidates.add(cnt_sort[i][0]-1)
  candidates.add(cnt_sort[i][0]+1)

# 配列に渡された配列内に，±1で数xに出来る数がいくつあるか判定
def neigh(array, x):
  cnt = 0
  for a in array:
    if a == x:
      cnt+=1
    elif a-1 == x:
      cnt+=1
    elif a+1 == x:
      cnt+=1
  return cnt

res=[]
for c in candidates:
  res.append(neigh(A,c))
  
print(max(res))

### FIXED CODE ###

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

cnt=dict()
# a内の数とその±1をdict型の配列に入れながら個数をカウント
for a in A:
  cnt[a] = cnt.setdefault(a,0) + 1
  cnt[a-1] = cnt.setdefault(a-1,0) + 1
  cnt[a+1] = cnt.setdefault(a+1,0) + 1
  
  
# カウントした数字で昇順にソート  
cnt_sort = sorted(cnt.items(), key=lambda x:x[1])
cnt_sort.reverse()

print(cnt_sort[0][1])
### BUGGY CODE ###

num = []
for _ in range(int(input())):
    num.append(int(input()))

for i in range(len(num)):
    a = num[:i]
    b = num[i+1:]
    c = a + b
    print(max(c))

### FIXED CODE ###

num = []
aaa = []
nmax = 0
n2max = 0
count = 0
n = int(input())
for i in range(n):
    a = int(input())
    aaa.append(a)
    if(nmax < a):
        n2max = nmax
        nmax = a
        count = 1
        num = [i]
    elif(nmax == a):
        count += 1
        num.append(i)
    elif(n2max < a):
        n2max = a
for i in range(len(aaa)):
    if(count >= 2) or (nmax != aaa[i]):
        print(nmax)
    else:
        print(n2max)
### BUGGY CODE ###

#<122>
N, Q = map(int,input().split())
S = input()
for q in range(Q):
    get_ac = ""
    l, r = map(int,input().split())
    get_ac = S[l-1:r]
    print(get_ac.count("AC"))
    


### FIXED CODE ###

from itertools import accumulate
N, Q = map(int,input().split())
S = input()
A = [list(map(int,input().split())) for q in range(Q)]
#print(A)

#フラグを立てて累積和で高速化
flg = []
for n in range(N-1):
    tmp_s = S[n:n+2]
    if tmp_s == "AC":
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))
#print(flg2)

for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])