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

import itertools

n = int(input())
s = [int(input()) for s in range(n)]
max0 = 0
for i in range(n):
    s2 = list(itertools.permutations(s, i+1))
    for comb in s2:
        tmax =sum(comb)
        if tmax%10 != 0: 
            max0 = max(max0,sum(comb))
print(max0)

### FIXED CODE ###

n = int(input())
s = [int(input()) for s in range(n)]
s1 = []
sum0 = 0
for i in s:
    if i%10 == 0:
        sum0 += i
    else:
        s1.append(i)

if len(s1) == 0:
    print(0)
else:
    sum1 = sum(s1)
    if sum1%10 != 0:
        print(sum0 + sum1)
    else:
        print(sum0 + sum1 - min(s1))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
for i in range(w):
  if s[0][i]=='.':
    u[0][i]=1
  for j in range(1,h):
    if s[j][i]=='.':
      u[j][i]+=u[j-1][i]+1
for i in range(w):
  if s[h-1][i]=='.':
    d[h-1][i]=1
  for j in range(h-2,-1,-1):
    if s[j][i]=='.':
      d[j][i]+=d[j+1][i]+1
for i in range(h):
  if s[i][0]=='.':
    l[i][0]=1
  for j in range(1,w):
    if s[i][j]=='.':
      l[i][j]+=l[i][j-1]+1
for i in range(h):
  if s[i][w-1]=='.':
    r[i][w-1]=1
  for j in range(w-2,-1,-1):
    if s[i][j]=='.':
      r[i][j]+=r[i][j+1]+1
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      ans=max(ans,u[i][j]+d[i][j]+l[i][j]+r[i][j]-3)
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      d[i][j]=0
      l[i][j]=0
    else:
      if i!=0:
        d[i][j]+=d[i-1][j]+1
      else:
        d[i][j]=1
      if j!=0:
        l[i][j]+=l[i][j-1]+1
      else:
        l[i][j]=1
for i in range(h)[::-1]:
  for j in range(w)[::-1]:
    if s[i][j]=='#':
      r[i][j]=0
      u[i][j]=0
    else:
      if i!=h-1:
        u[i][j]+=u[i+1][j]+1
      else:
        u[i][j]=1
      if j!=w-1:
        r[i][j]+=r[i][j+1]+1
      else:
        r[i][j]=1
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      ans=max(ans,u[i][j]+d[i][j]+l[i][j]+r[i][j]-3)
print(ans)
### BUGGY CODE ###

# coding: utf-8

n = int(input().rstrip())
bo = [j * -1 for j in sorted([int(i) * -1 for i in input().rstrip().split(" ")])]

def get_count(start:int, num:int):
    if bo[len(bo)-1] > num:
        return len(bo)-1
    if bo[start] <= num:
        return -1
    return get_count_sub(start, len(bo)-1, num)

def get_count_sub(min:int, max:int, target:int):
    if max - min <= 1:
        if bo[max] > target:
            return max
        else:
            return min

    mid = int((max+min)/2)
    if bo[mid] > target:
        return get_count_sub(mid, max, target)
    else:
        return get_count_sub(min, mid, target)

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j < int(i/2):
            break
        idx = get_count(j + 1, bo[i] - bo[j])
        if idx < 0:
            break
        ans += idx - j

print(ans)


### FIXED CODE ###

# coding: utf-8
from bisect import bisect_left, bisect_right

n = int(input().rstrip())
bo = sorted([int(i) * -1 for i in input().rstrip().split(" ")])

def get_count(start:int, num:int):
    if bo[len(bo)-1] > num:
        return len(bo)-1
    if bo[start] <= num:
        return -1
    return get_count_sub(start, len(bo)-1, num)

def get_count_sub(min:int, max:int, target:int):
    if max - min <= 1:
        if bo[max] > target:
            return max
        else:
            return min

    mid = int((max+min)/2)
    if bo[mid] > target:
        return get_count_sub(mid, max, target)
    else:
        return get_count_sub(min, mid, target)

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j < int(i/2):
            break
        idx = bisect_left(bo, bo[i]-bo[j], j+1)
        ans += idx - j - 1

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

N, Q = map(int, input().split())
S = input()

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

#print(C)

for q in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1

  ans = sum(C[l:r])
  print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

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

#print(C)

for q in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1

  ans = C[r-1] - C[l-1]
  print(ans)
### BUGGY CODE ###

n = int(input())
alist = [int(s) for s in input().split(" ")]
adict = {}
for a in alist:
  if a in adict:
    adict[a] += 1
  else:
    adict[a] = 1
q = int(input())
bclist = []
for _ in range(q):
  b, c = [int(s) for s in input().split(" ")]
  bclist.append([b, c])

for b, c in bclist:
  if c in adict and b in adict:
    adict[c] += adict[b]
    del adict[b]
  elif b in adict:
    adict[c] = adict[b]
    del adict[b]
  ans = 0
  for k, v in adict.items():
    ans += k * v
  print(ans)

### FIXED CODE ###

n = int(input())
alist = [int(s) for s in input().split(" ")]
adict = {}
ans = 0
for a in alist:
  ans += a
  if a in adict:
    adict[a] += 1
  else:
    adict[a] = 1
q = int(input())
bclist = []
for _ in range(q):
  b, c = [int(s) for s in input().split(" ")]
  bclist.append([b, c])

for b, c in bclist:
  if c in adict and b in adict:
    ans += (c - b) * adict[b]
    adict[c] += adict[b]
    del adict[b]
  elif b in adict:
    ans += (c - b) * adict[b]
    adict[c] = adict[b]
    del adict[b]
  print(ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
a = list(map(int, input().split()))
A = np.array(a)

for i in range(M):
  x = A.argmax()
  if A[x] == 0:
    break
  A[x] >>= 1

print(sum(A))



### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

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

import sys
S=input()
Q=int(sys.stdin.readline())
flag=0
for i in range(Q):
	qu=input()
	if qu[0]=='1':
		if flag==0:
			flag+=1
		else:
			flag=0
	else:
		if qu[2]=='1' and flag==0:
			S=qu[4]+S
		elif qu[2]=='1' and flag==1:
			S+=qu[4]
		elif qu[2]=='2' and flag==0:
			S+=qu[4]
		else:
			S=qu[4]+S
if flag==1:
	S=S[::-1]
print(S)

### FIXED CODE ###

import sys
from collections import deque
S=[input()]
S=deque(S)
Q=int(sys.stdin.readline())
flag=0
for i in range(Q):
	qu=tuple(input().split())
	if qu[0]=='1':
		if flag==0:
			flag+=1
		else:
			flag=0
	else:
		if qu[1]=='1' and flag==0:
			S.appendleft(qu[2])
		elif qu[1]=='1' and flag==1:
			S.append(qu[2])
		elif qu[1]=='2' and flag==0:
			S.append(qu[2])
		elif qu[1]=='2' and flag==1:
			S.appendleft(qu[2])
if flag==1:
	S=''.join(S)
	S=S[::-1]
	print(S)
	exit()
print(''.join(S))
### BUGGY CODE ###

s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
for i in range(len(s)):
    arr.append(int(s[-(i+1):])%2019)

for i in range(len(arr)):
    amari[arr[i]] +=1    
    
for i in amari:
    ans = ans + i * (i-1) // 2
print(ans)

### FIXED CODE ###

s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
cnt = 0
keta = 1
for i in range(len(s)):
    cnt = (cnt + int(s[-(i+1)]) * keta) % 2019
    arr.append(cnt)
    keta =keta * 10 % 2019

for i in range(len(arr)):
    amari[arr[i]] +=1    
    
for i in amari:
    ans = ans + i * (i-1) // 2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => O(N)で解く
dp = [0] * N
dp[0] = 1
mod = 998244353
 
for i in range(N):
  for j in range(K):
    L = X[j][0]
    R = X[j][1]
    for k in range(L, R+1):
      if 0 <= i - k < N-1:
        dp[i] += dp[i-k]
        dp[i] %= mod
      else: continue

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
 
# dpの高速化 => 累積和によって、O(N)で解く
dp = [0] * N
acc = [0]* (N+1)
dp[0], acc[1] = 1, 1
# acc[0] = 0
# acc[1] = dp[0]
# acc[2] = dp[0] + dp[1]
# acc[n] = dp[0] + dp[1] + dp[n-1]

# dp[0] = acc[1] - acc[0]
# dp[1] = acc[2] - acc[1]
# dp[n-1] = acc[n] - acc[n-1]
mod = 998244353
 
for i in range(1, N):
  # acc[i] = dp[0] + ... + dp[i-1] が既知
  # 貰うdp
  for j in range(K):
    r = i - X[j][0]
    l = i - X[j][1]
    if r < 0: continue
    l = max(l, 0)
      
    dp[i] += acc[r+1] - acc[l] # s = dp[L] + ... + dp[R]
    dp[i] %= mod
  acc[i+1] = acc[i] + dp[i] # acc[i+1] = dp[0] + ... + dp[i]

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

h, w = map(int, input().split())

s = [input() for i in range(h)]

board = [[[0 for _ in range(2)] for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board[i][j][0] = cnt_continue
    for j in reversed(range(w-1)):
        if board[i][j][0] == 0:
            continue
        board[i][j][0] = max(board[i][j][0], board[i][j+1][0])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board[j][i][1] = cnt_continue

    for j in reversed(range(h-1)):
        if board[j][i][1] == 0:
            continue
        board[j][i][1] = max(board[j][i][1], board[j+1][i][1])


ans = 0

for i in range(h):
    for j in range(w):
        v = sum(board[i][j]) - 1
        ans = max(ans, v)

print(ans)


### FIXED CODE ###

h, w = map(int, input().split())

s = [input() for i in range(h)]

board_w = [[0 for _ in range(w)] for _ in range(h)]
board_h = [[0 for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_w[i][j] = cnt_continue

    for j in reversed(range(w-1)):
        if board_w[i][j] == 0:
            continue
        board_w[i][j] = max(board_w[i][j], board_w[i][j+1])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_h[j][i] = cnt_continue

    for j in reversed(range(h-1)):
        if board_h[j][i] == 0:
            continue
        board_h[j][i] = max(board_h[j][i], board_h[j+1][i])


ans = 0

for i in range(h):
    for j in range(w):
        v = board_w[i][j] + board_h[i][j] - 1
        ans = max(ans, v)

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

n=int(input())
count=[[0 for i in range(10)] for j in range(9)]
ans=0
for i in range(1,n+1):
    num=list(str(i))
    l,r=eval(num[0]),eval(num[-1])
    #print(str(l)+"  "+str(r))
    #print(l+r)
    count[l-1][r]+=1
#print(count)
for i in range(1,10):
    for j in range(1,10):
        if i==j:
            continue
        ans+=(count[i-1][j])*(count[j-1][i])
for i in range(1,10):
    ans+=(count[i-1][i]**2)
print(ans)

### FIXED CODE ###

n=int(input())
count=[[0 for i in range(10)] for j in range(9)]
ans=0
num=1
zero=0
for i in range(1,n+1):
    if (10**(zero+1))<=num:
        zero+=1
    a=i//10
    r=i-a*10
    l=i//(10**zero)
    count[l-1][r]+=1
    num+=1
#print(count)
for i in range(1,10):
    for j in range(1,10):
        if i==j:
            continue
        ans+=(count[i-1][j])*(count[j-1][i])
for i in range(1,10):
    ans+=(count[i-1][i]**2)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge[l] = next
                    l += 1
                    d[i][next] = d[i][q]+c
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    d[i][next] = d[i][q]+c
                    if not(next in hoge[:l]):
                        hoge[l] = next
                        l += 1
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)
### BUGGY CODE ###

N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(X+1, Y):
    dist[i] = min(dist[i-1]+1, dist[i+1]+1, dist[i])
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist


for i in range(N):
  dist_map[i] = search(i)

#print(N)
count = [0 for i in range(N)]
for i in range(N):
  #print('i='+str(i))
  #dist = dist_map[i]
  #print(*dist)
  dist = dist_map[i]
  for dis in dist:
    count[dis] += 1
for i in range(1, N):
  print(count[i]//2)

### FIXED CODE ###

N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist

count = [0 for i in range(N)]
for i in range(N):
  dist = search(i)
  for dis in dist:
    count[dis] += 1

for i in range(1, N):
  print(count[i]//2)
### BUGGY CODE ###

def p(b):
    for i in range(0,len(b)):
        if i==len(b)-1:
            print(b[i])
        else:
            print(b[i],' ',end="")
n=int(input())
e=[int(i) for i in input().split()]
b=[]
for i in range(0,n):
    b.append(e.pop(0))
    b.reverse()
p(b)


### FIXED CODE ###

def p(b):
    for i in range(0,len(b)):
        if i==len(b)-1:
            print(b[i])
        else:
            print(b[i],' ',end="")

n=int(input())
a=[int(i) for i in input().split()]
b=[None]*n
if n%2==1:
    m=int(n/2)
    b[m]=a[0]
    s=1
    t=1
    while s+m<n:
        b[m+s]=a[t]
        t+=1
        b[m-s]=a[t]
        t+=1
        s+=1
    p(b)
else:
    m=int(n/2)
    b[m]=a[0]
    s=1
    t=1
    while s+m<=n:
        b[m-s]=a[t]
        t+=1
        if m-s==0:
            break
        b[m+s]=a[t]
        t+=1
        s+=1
    p(b)
### BUGGY CODE ###

n=int(input())
s=[''.join(sorted(input())) for i in range(n)]
a=list(set(s))
cnt=0
for i in a:
  j=s.count(i)
  cnt+=j*(j-1)//2
print(cnt)

### FIXED CODE ###

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

c=[]
i=0
while i<n-1:
  cnt=0
  while i<n-1 and s[i]==s[i+1]:
    cnt+=1
    i+=1
  c+=[cnt+1]
  i+=1
ans=0
for i in c:
  if i>1:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

inf=10**8

n,m=map(int,input().split())

A=[]
C=[]
dp=[inf]*(1<<n)
dp[0]=0

for _ in range(m):
  a,_=map(int,input().split())
  c=list(map(int,input().split()))
  A.append(a)
  tmp=0
  for i in c:
    tmp+=1<<(i-1)
  C.append(tmp)

for i in range(1<<n):
  for index,j in enumerate(C):
    dp[i|j]=min(dp[i|j],dp[i]+A[index])
ans=dp[-1]
if ans==inf:ans=-1
print(ans)

### FIXED CODE ###

inf=10**8

n,m=map(int,input().split())

A=[]
C=[]
dp=[inf]*(1<<n)
dp[0]=0

for _ in range(m):
  a,_=map(int,input().split())
  c=list(map(int,input().split()))
  A.append(a)
  tmp=0
  for i in c:
    tmp+=1<<(i-1)
  C.append(tmp)

for i in range(1<<n):
  for index,j in enumerate(C):
    dp[i|j]=min(dp[i|j],dp[i]+A[index])
ans=dp[-1]
if ans==inf:ans=-1
print(ans)
### BUGGY CODE ###

import itertools

n = int(input())

s = [0 for _ in range(n)]
in_a = [0 for _ in range(n)]
dic_tmp = {}
dic_ar = [0 for _ in range(n)]
for i in range(n):
    in_a[i] = input()

for i in range(n):
    dic_tmp = {}
    for ss in in_a[i]:
        dic_tmp[ss] = dic_tmp.get(ss,0) + 1
    
    dic_ar[i] = dic_tmp

cnt = 0
for i in range(n):
    for j in range(n):
        if(i == j):
            continue
        hantei = len(dic_ar[i].items() ^ dic_ar[j].items())

        if(hantei == 0):
            cnt += 1

print(cnt//2)



### FIXED CODE ###

import itertools

n = int(input())

s = [0 for _ in range(n)]
in_a = [0 for _ in range(n)]
dic_tmp = {}
dic_ar = [0 for _ in range(n)]
for i in range(n):
    in_a[i] = input()

cnt = 0
for i in range(n):
    s = sorted(in_a[i])
    s = "".join(s)
    if(s in dic_tmp):
        cnt += dic_tmp[s]
        dic_tmp[s] += 1
    else:
        dic_tmp[s] = 1

print(cnt)
### BUGGY CODE ###

import random
D=int(input())
c=input().split()
c=[int(a) for a in c]
S=[]
for _ in range(D):
    s=input().split()
    s=[int(a) for a in s]
    S.append(s)
answers=[]
scores=[]
numbers=[]
for _ in range(1500000):
    d=random.randrange(0,26,1)
    q=random.randrange(0,26,1)
    numbers.append([d,q])
whole=sum(c)
suuji=1
T=[]
while suuji<=365:
    T.append(random.randrange(0,26,1))
    suuji+=1
for m in range(1500000):
    anss=[]
    ans = 0
    held = [0 for _ in range(26)]
    e=numbers[m][0]
    q=numbers[m][1]
    a=T[e]
    T[e]=q
    wholes=0
    for d in range(D):
        s = S[d]
        place = T[d]
        ans += s[place]
        wholes+=whole
        wholes-=c[place]*((d+1)-held[place])
        held[place] = d + 1
        ans-=wholes
    scores.append(ans)
    answers.append(T)
saidai=max(scores)
basho=scores.index(saidai)

answer=answers[basho]
for answer_ in answer:
    print(answer_+1)


### FIXED CODE ###

D=int(input())
c=input().split()
c=[int(a) for a in c]
S=[]
for _ in range(D):
    s=input().split()
    s=[int(a) for a in s]
    S.append(s)

for d in range(D):
    if d%27==0:
        print(20)
    else:
        print(d%27)
### BUGGY CODE ###

A,B,C = map(int,input().split(" "))
p_flag = 0
D = 0
i = 0
limit = A+B+C+1
while True:
    if p_flag == 0 and C >= 1:
        p_flag = 1
        D += 1
        C -= 1
    elif p_flag == 1 and B >= 1:
        p_flag = 0
        D += 1
        B -= 1
    elif p_flag == 1 and A >= 1:
        p_flag = 0
        A -= 1
    elif B >= 1:
        p_flag = 0
        D += 1
        B -= 1
    elif A >= 1:
        p_flag = 0
        A -= 1
    elif C >= 1:
        if p_flag == 1:
            break
        p_flag = 1
        D += 1
        C -= 1
    i += 1
    if i >= limit:
        break
print(D)

### FIXED CODE ###

A,B,C = map(int,input().split(" "))
D = 0

if (A+B) >= C:
    D += B + C
elif C >= B:
    D += B * 2
    C -= B
    if C >= A:
        D += A
        C -= A
        if C >= 1:
            D += 1
print(D)
### BUGGY CODE ###

q = int(input())

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

def primes(n):
    # 1であれば素数であるリスト
    primes = [1] * (n+1)
    primes[0] = 0
    primes[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not primes[i]:
            continue
        for j in range(i * 2, n + 1, i):
            primes[j] = 0
    return primes

MAX = 100000
prime_cumsum = primes(MAX)
# 2017に似た数値かどうかを更新
for i in range(MAX, -1, -1):
    if prime_cumsum[i] == 0:
        continue
    if prime_cumsum[(i+1)//2] == 0:
        prime_cumsum[i] = 0

for i in range(q):
    print(sum(prime_cumsum[lr[i][0]:lr[i][1]+1]))

### FIXED CODE ###

q = int(input())

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

def primes(n):
    # 1であれば素数であるリスト
    primes = [1] * (n+1)
    primes[0] = 0
    primes[1] = 0

    for i in range(2, int(n**0.5) + 1):
        if not primes[i]:
            continue
        for j in range(i * 2, n + 1, i):
            primes[j] = 0
    return primes

MAX = 100000
prime_list = primes(MAX)

# 2017に似た数値かどうかを求めるための累積和用のリスト作成
ans_list = [0] * (MAX + 1)
now = 0
for i in range(MAX):
    if prime_list[i] == 1 and prime_list[(i+1)//2] == 1:
        now += 1
    ans_list[i+1] = now

for i in range(q):
    print(ans_list[lr[i][1]+1] - ans_list[lr[i][0]])