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

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,q = map(int, input().split())
    s = input()
    for _ in range(q):
        res = 0
        l, r = map(int, input().split())
        moji = s[l-1:r]
        for i in range(len(moji)-1):
            if moji[i]=='A' and moji[i+1]=='C':
                res += 1
        print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,q = map(int, input().split())
    s = input()
    l = [0]*(n+1)
    for i in range(n):
        if s[i:i+2]=='AC':
            l[i+1]=l[i] + 1
        else:
            l[i+1]=l[i]

    for _ in range(q):
        a, b = map(int, input().split())
        print(l[b-1]-l[a-1])


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

n=int(input())
print(1)
s=input()
if s="Vacant":
  exit(0)

l=1
r=n

for i in range(20):

  if r-l<=2:
    for j in range(3):
      print(l+j, flush=True)
      s=input()
      if s="Vacant":
        exit(0)

      
  elif (r-l+1)%4==1:
    print((l+r)//2, flush=True)
    sn=input()
    if sn="Vacant":
      exit(0)
    elif s==sn:
      l=(l+r)//2
    else:
      r=(l+r)//2
    s=sn

  else:
    print((l+r)//2-1, flush=True)
    sn=input()
    if sn="Vacant":
      exit(0)
    elif s==sn:
      l=(l+r)//2-1
    else:
      r=(l+r)//2-1
    s=sn

### FIXED CODE ###

n=int(input())
print(0, flush=True)
sl=input()
if sl=="Vacant":
  exit(0)

l=0
r=n-1

for i in range(30):

  if r-l<=2:
    for j in range(3):
      print(l+j+1, flush=True)
      s=input()
      if s=="Vacant":
        exit(0)

      
  elif ((l+r)//2)%2==0:
    print((l+r)//2, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s

  else:
    print((l+r)//2+1, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s
### BUGGY CODE ###

n=int(input())
s=input();ew=[]
ans=[]
for i in s:
	if i=='W': ew.append(0)
	else: ew.append(1)

for i in range(n):
	t=[]
	t.extend([1]*i)
	t.append(ew[i])
	t.extend([0]*(n-i-1))
	a=list(map(lambda x,y: abs(x-y), ew,t))
	ans.append(sum(a))
print(min(ans))

### FIXED CODE ###

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

num_w=0
num_e=s[1:].count('E')
ans=num_e
for i in range(n):
	if i == 0:
		continue
	if s[i]=='E':
		num_e-=1
	if s[i-1]=='W':
		num_w+=1
	ans=min(ans, num_w+num_e)
print(ans)
### BUGGY CODE ###

x, y, z, K = map(int, input().split())

A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

temp = []
for a in A:
	for b in B:
		temp.append(a+b)

temp = sorted(temp, reverse=True)
temp = temp[:K]

ans = []
for c in C:
	for num in temp:
		ans.append(num+c)

ans = sorted(ans, reverse=True)
for i in range(K):
	print(ans[i])


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n + 1):
    if i == 0: continue
    ans.append(a.count(i))

for i in range(n):
    print(ans[i])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = []
sp = 0
c = 0
for i in range(n + 1):
    if i == 0: continue
    for j in range(sp, n - 1):
        if a[j] != i:
            break
        sp += 1
        c += 1
    ans.append(c)
    c = 0

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
#L.sort()
cnt = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      if L[i] + L[j] > L[k] and L[j] + L[k] > L[i] and L[k] + L[i] > L[j]:
        cnt += 1
      else:
        pass
#      else:
#        break
print(cnt)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
cnt = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    cnt += bisect_left(L, L[i] + L[j]) - j - 1
print(cnt)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.empty((0,2),int)
for i in range(n):
    b = np.array([[int(i) for i in input().split()]])
    a = np.append(a,b,axis=0)
a = a[np.argsort(a[:, 1])]
ans = "Yes"
k = 0
for i in range(len(a)):
    k += a[i,0]
    if k > a[i,1]:
        ans = "No"
        break
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
a.sort(key=itemgetter(1))
ans = "Yes"
k = 0
for i in range(len(a)):
    k += a[i][0]
    if k > a[i][1]:
        ans = "No"
        break
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
d=[0]*N
ans=0
for i in range(N):
    d[a[i]-1]+=1
d.sort()
while len(d)>K:
    ans += d[0]
    d.pop(0)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
d=[0]*N
ans=0
for i in range(N):
    d[a[i]-1]+=1
d.sort(reverse=True)
if len(d)>K:
    ans =sum(d[K:])
print(ans)
### BUGGY CODE ###


MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += a[i] ^ a[j]
        ans %= MOD

print(ans)


### FIXED CODE ###


n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit_one_count = [0 for i in range(60)]
bit_zero_count = [0 for i in range(60)]
for i in range(n):
    bits = '{0:060b}'.format(a[i])
    for j in range(60):
        if bits[-1 -j] == '1':
            bit_one_count[j] += 1
        else:
            bit_zero_count[j] += 1

ans = 0
for j in range(60):
    ans += bit_one_count[j] * bit_zero_count[j] * 2 ** j
    ans %= MOD

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

from collections import Counter
N=int(input())
S=list()
Y=list()
for i in range(N):
    S.append(input())
X=Counter(S)
Y.append(X.most_common()[0][0])
for i in range(len(X)-1):
    if X.most_common()[i][1] == X.most_common()[i+1][1]:
        Y.append(X.most_common()[i+1][0])
    else:
        break
Y.sort()
for i in range(len(Y)):
    print(Y[i])


### FIXED CODE ###

from collections import Counter
N=int(input())
S=list()
Y=list()
for i in range(N):
    S.append(input())
X=Counter(S)
F=X.most_common()[0][1]
keys = [k for k, v in X.items() if v == F]
keys.sort()
for i in range(len(keys)):
    print(keys[i])
### BUGGY CODE ###

import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue.Queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put((hi,wi,0))
				
	max_dist=0
	while not open_list.empty():
		hi, wi, d = open_list.get()
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			dist[hi+dh][wi+dw]=d+1
			open_list.put((hi+dh,wi+dw,d+1))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
#import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

class queue:
	def __init__(self):
		self.l=[0]*(1000*1000+100)
		self.f=0
		self.t=0
		
	def put(self,v):
		self.l[self.f]=v
		self.f+=1
		
	def get(self):
		self.t+=1
		return self.l[self.t-1]
		
	def empty(self):
		return self.f==self.t

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put(hi*2000+wi)
				
	max_dist=0
	while not open_list.empty():
		hi_wi = open_list.get()
		hi = hi_wi // 2000
		wi = hi_wi % 2000
		d = dist[hi][wi]
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			#if dist[hi+dh][wi+dw]==-2:
				
			dist[hi+dh][wi+dw]=d+1
			open_list.put(((hi+dh)*2000+wi+dw))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
v = S.values()
if len(S) == 1:
    print(list(S)[0])
    exit()

for x in sorted([key for key, val in list(S.most_common()) if val == max(v)]):
    print(x)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
v = max(S.values())
s = sorted(S.most_common())
if len(S) == 1:
    print(list(S)[0])
    exit()
for k, val in s:
    if val == v:
        print(k)
### BUGGY CODE ###

# AGC 007: A – Shik and Stone
H, W = [int(s) for s in input().split()]
A = [input() for _ in range(H)]

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]

    if (i + 1 < H and A[i + 1][j] != '#') and (j + 1 < W and A[i][j + 1] != '#'):
        isExact = 'Impossible'
        break
    if j + 1 < W and A[i][j + 1] == '#':
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        i += 1

if isExact == 'Possible':
    A[H - 1] = A[H - 1][:W - 1] + '.'

    for line in A:
        if '#' in line:
            isExact = 'Impossible'
            break

print(isExact)

### FIXED CODE ###

# AGC 007: A – Shik and Stone
h, w = [int(s) for s in input().split()]
a = [input() for _ in range(h)]

the_number_of_stones = 0

for i in range(h):
    the_number_of_stones += a[i].count('#')

print('Possible' if the_number_of_stones == h + w - 1 else 'Impossible')
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
l = int(((N**2)+1)/2)
b = []
for i in range(l):
    b.append([1,-1])
b = np.array(b).reshape(1,2*l)
c = (np.delete(b, 2*l-1, axis=None)).reshape(N,N)
d = c.reshape(N,N)
inv = 0.5*( np.triu(c) - ( np.tril(c) - np.eye(N) ) )
g = np.eye(N)
x = 2*(np.dot(inv,a))
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
# l = int(((N*N)+1)/2)
b = []
for i in range(N):
    if i%2==0:
        b.append(1)
    else:
        b.append(-1)
c = np.dot(np.array(b),a)
x = [c]
for j in range(1,N):
    x_j = 2*a[j-1] - x[j-1]
    x.append(x_j)
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))
### BUGGY CODE ###

from itertools import product
from functools import reduce
import math
 
def gcd(tup):
  return reduce(lambda a, b: math.gcd(a, b), tup)


K = int(input())
lst = range(1, K+1)
Sum = 0

for tup in product(lst, lst, lst):
  Sum += gcd(tup)
  
print(Sum)

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
### BUGGY CODE ###

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

i = 1
if 1 in a:
    while i in a:
        del a[:a.index(i)]
        i += 1
    print(n-i+1)
else:
    print(-1)

### FIXED CODE ###

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

for i in a:
    if k == i:
        k += 1

if k == 1:
    print(-1)
else:
    print(n-k+1)
### BUGGY CODE ###

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

n = 0

for i in range(k + 1):
  for j in range(k + 1):
    for l in range(k + 1):
      if i + j + l == s:
        n += 1
        
print(n)

### FIXED CODE ###

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

n = 0

for i in range(k + 1):
  for j in range(k + 1):
    dif = s - (i + j)
    if dif >= 0 and dif <= k:
      n += 1
        
print(n)
### BUGGY CODE ###

import re
                                         
S = input()
T = S
while True:
    if re.search("dreamer$", T):
        T = T[:-7]
    elif re.search("eraser$", T):
        T = T[:-6]
    elif re.search("(dream|erase)$", T):
        T = T[:-5]
    else:
        print("NO")
        break
    if T == "":
        print("YES")
        break

### FIXED CODE ###

import re
                                      
S = input()
S = re.sub("eraser", "", S)
S = re.sub("erase", "", S)
S = re.sub("dreamer", "", S)
S = re.sub("dream", "", S)
print("YES" if len(S) == 0 else "NO")
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A].append(-B)
# print(dic, sorted(dic.keys()))

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        heap.extend(dic[i + 1])
    heapq.heapify(heap)
    # print(heap)
    if heap:
        ans = ans - heapq.heappop(heap)

print(ans)


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A].append(-B)
# print(dic, sorted(dic.keys()))

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        for j in dic[i + 1]:
            heapq.heappush(heap, j)
    # print(heap)
    if heap:
        ans = ans - heapq.heappop(heap)

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

s = input()
num = len(s)

l = []
for _ in range(1, 20190000):
    if _%2019 == 0:
        l.append(_)
l = set(l)
#print(l)

def aaa(s, num):
    x = 0
    for i in range(4,num+1):
        for j in range(num - i + 1):
            if int(s[j:j+i]) in l:
                x += 1
    print(x)

aaa(s, num)

### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

# flip = True:その場が黒
def dfs(flip, nowx, nowy, step):
    if nowx == gx and nowy == gy:
        if field[nowy][nowx] == '#':
            step += 1
        elif field[nowy][nowx] == '.' and flip:
            step += 1
        return step
    else:
        if field[nowy][nowx] == '.':
            if flip:
                step += 1
                flip = False
        elif field[nowy][nowx] == '#':
            if flip == False:
                flip = True
        if nowx + 1 == w:
            return dfs(flip, nowx, nowy + 1, step)
        if nowy + 1 == h:
            return dfs(flip, nowx + 1, nowy, step)
        return min(dfs(flip, nowx + 1, nowy, step),
                   dfs(flip, nowx, nowy + 1, step))


h, w = map(int, input().split())
field = [[c for c in input().strip()] for _ in range(h)]
sx, sy = 0, 0
gx, gy = w - 1, h - 1
dirx = [1, 0]
diry = [0, 1]

print(dfs(False, sx, sy, 0))


### FIXED CODE ###

h, w = map(int, input().split())
field = [[c for c in input().strip()] for _ in range(h)]
sx, sy = 0, 0
gx, gy = w - 1, h - 1
dirx = [1, 0]
diry = [0, 1]
inf = 1001001001
dp = [[(inf, False) for _ in range(w)] for _ in range(h)]
flip = False
step = 0
for i in range(w):
    if field[0][i] == '.':
        if flip:
            step += 1
            flip = False
    elif field[0][i] == '#':
        if flip == False:
            flip = True
    dp[0][i] = (step, flip)

flip = False
step = 0
for i in range(h):
    if field[i][0] == '.':
        if flip:
            step += 1
            flip = False
    elif field[i][0] == '#':
        if flip == False:
            flip = True
    dp[i][0] = (step, flip)

for i in range(1, h):
    for j in range(1, w):
        tmp1, f1 = dp[i - 1][j]
        tmp2, f2 = dp[i][j - 1]
        if field[i][j] == '.':
            if f1:
                tmp1 += 1
                #f1 = False
            if f2:
                tmp2 += 1
                #f2 = False
            dp[i][j] = (min(tmp1, tmp2), False)
        else:
            if i == gy and j == gx:
                dp[i][j] = (min(tmp1 + 1, tmp2 + 1), True)
            else:
                dp[i][j] = (min(tmp1, tmp2), True)

print(dp[h - 1][w - 1][0])
### BUGGY CODE ###

import bisect


N = int(input())
s = []
memo = [{} for _ in range(N)]
for i in range(N):
    si = list(input())
    si.sort()
    s += [('').join(si)]
s.sort()
ans = 0
while (s):
    t = bisect.bisect_right(s, s.pop(0))
    ans += t
print(ans)

### FIXED CODE ###

N = int(input())
memo = {}
ans = 0
for i in range(N):
    si = list(input())
    si.sort()
    si = ('').join(si)
    if si not in memo:
        memo[si] = 1
    else:
        memo[si] += 1
        ans += memo[si] - 1
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
N, M = map(int, input().split())
Data = [list(map(int, input().split())) for _ in range(N)]

heap = [0] * M
ans = 0
for i in range(1, M+1):
    N = len(Data)
    for j in range(N-1, -1, -1):
        if (Data[j][0] <= i):
            heappush(heap, -(Data.pop(j)[1]))

    ans += -(heappop(heap))

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
N, M = map(int, input().split())

Data = [list(map(int, input().split())) for _ in range(N)]
Data.sort(reverse = True)

heap = [0] * M
ans = 0
for i in range(1, M+1):
    N = len(Data)
    for j in range(N-1, -1, -1):
        if Data[j][0] > i:
            break
        if (Data[j][0] <= i):
            heappush(heap, -(Data.pop(j)[1]))

    ans += -(heappop(heap))

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

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

ans=0

for i in range(1,2**n):
    count=0
    num=0
    for j in range(n):
        if (i>>j)&1==1:
            count+=1
            num+=x[j]
    if num%count==0 and num//count==a:
        ans+=1

print(ans)

### FIXED CODE ###

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

for i in range(n):
    x[i]-=a
    
dp=[0]*(2*n*50+2)
dp[0]=1
for i in range(n):
    h=dp[:]
    for j in range(-(n-1)*50,(n-1)*50+1):
        h[j]+=dp[j-x[i]]
    dp=h
print(dp[0]-1)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
Exp = [list(map(int,input().split())) for i in range(M)]
Exp.sort()
memo = [[0 for i in range(N)] for j in range(N)]
for e in Exp:
    memo[e[0]-1][e[1]-1] += 1
for i in range(N):
    for j in range(N):
        if i < j:
            memo[i][j] += memo[i][j-1] + sum(memo[j-k][j] for k in range(j-i))
Query = [list(map(int,input().split())) for i in range(Q)]
for q in Query:
    print(memo[q[0]-1][q[1]-1])

### FIXED CODE ###

N,M,Q = map(int,input().split())
memo = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    memo[l][r] += 1
for i in range(N):
    for j in range(N):
        memo[i+1][j+1] += memo[i][j+1] + memo[i+1][j] - memo[i][j]
for i in range(Q):
    p,q = map(int,input().split())
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    S = list(str(input().strip()))
    n = len(S)

    dp = [[0] * 13 for _ in range(n)]
    s = S.pop()
    if s == '?':
        for i in range(10):
            dp[0][i] = 1
    else:
        s = int(s)
        dp[0][s] = 1

    digit = 1
    m = 1
    while S:
        s = S.pop()
        m = (m * 10) % 13
        if s == '?':
            for k in range(10):
                M = (m * k) % 13
                for i in range(13):
                    j = (i + M) % 13
                    dp[digit][j] += dp[digit-1][i]
                    dp[digit][j] %= MOD
        else:
            s = int(s)
            M = (m * s) % 13
            for i in range(13):
                j = (i + M) % 13
                dp[digit][j] += dp[digit-1][i]
                dp[digit][j] %= MOD
        digit += 1

    return dp[n-1][5]


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


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    T = list(str(input().strip()))
    S = [int(t) if t != '?' else -1 for t in T]
    n = len(S)

    dp = [[0] * 13 for _ in range(n)]
    s = S.pop()
    if s < 0:
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][s] = 1

    digit = 1
    m = 1
    while S:
        s = S.pop()
        m = (m * 10) % 13
        if s < 0:
            for k in range(10):
                M = (m * k) % 13
                for i in range(13):
                    j = (i + M) % 13
                    dp[digit][j] += dp[digit-1][i]
                    dp[digit][j] %= MOD
        else:
            M = (m * s) % 13
            for i in range(13):
                j = (i + M) % 13
                dp[digit][j] += dp[digit-1][i]
                dp[digit][j] %= MOD
        digit += 1

    return dp[n-1][5]


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

n = int(input())
l = []
for i in range(n):
  l.append(''.join(sorted(input())))
s = set(l)

from math import factorial as f
def c(n, k):
  return f(n)//(f(n-k)*f(k)) if n>=k else 0

print(sum(c(l.count(a), 2) for a in s))

### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
  l.append(''.join(sorted(input())))
l.sort()

cnt = 0
ans = 0
for i in range(n-1):
  if l[i+1] == l[i]:
    cnt += 1
    ans += cnt
  else:
    cnt = 0
print(ans)