Harryxun/stf_run huggingface dataset:
N=int(input())
A=list(map(int,input().split()))
l=[]
no_even=0
def no_even(A,N):
    flag=0
    for i in range(N):
        if A[i]%2==0:
            flag=1
            break
    if flag==0:
        return True
    else:
        return False

count=0

while no_even(A,N)==False:
    for i in range(N):
        if A[i]%2==0:
            l.append(A[i])
    flag=0
    for i in range(N):
        if A[i]==max(l) and flag==0:
            A[i]=int(A[i]/2)
            flag=1
        else:
            A[i]*=3
#    print(A)    
    count+=1
print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
def count_two(num):
    flag=0
    count=0
    while flag==0:
        if num%2==0:
            count+=1
            num=int(num/2)
        else:
            flag=1
    return count

ans=0
for temp in A:
    ans+=count_two(temp)
print(ans)
s = input()
t = input()
print(t + s)

### FIXED CODE ###

s, t = input().split()
print(t + s)
li = list(map(int, input().split()))
li.sort(*, key = None, reverse = True)
for i in range(len(li)):
    a = li[i]
    b = li[i +1]
print(a -b)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse = True)
i = 0
a = 0
b = 0
while i < n: 
    a = a +l[i]
    i += 2
i = 1
while i < n:
    b = b +l[i]
    i += 2
print(a -b)
def check(a, b):
  if b < a:
    a, b = b, a
  if b - a <= 1:
    return 2 * a - 2
  c = int((a * b - 1)**.5)
  assert(c**2 < a * b <= (c + 1)**2)
  return 2 * c - 1 - (c * (c + 1) >= a * b)

for _ in range(int(input())):
  print(check(*list(map(int, input().split()))))

### FIXED CODE ###

def check(a, b):
  if b < a:
    a, b = b, a
  if b - a <= 1:
    return 2 * a - 2
  d = a * b
  c, ng = a, b
  while ng - c > 1:
    mid = (ng + c) // 2
    if mid ** 2 < d:
      c = mid
    else:
      ng = mid
  return 2 * c - 1 - (c * (c + 1) >= a * b)

for _ in range(int(input())):
  print(check(*list(map(int, input().split()))))
s = list(input())
flagA = False
flagZ = False

if s[0] == 'A':
    flagA = True

# 文字列の両端から探索していきAのうち最左端にあるものZのうち最右端にあるものの要素数を記録　O(N/2)
i = 1
while not (flagA == True and flagZ == True):

    if s[i] == 'A' and flagA == False:
        a = i 
        flagA = True 
    if s[-i] == 'Z' and flagZ == False:
        z = len(s) - i
        flagZ = True
    
    i += 1
print(z-a+1)

### FIXED CODE ###

s = list(input())
flagA = False
flagZ = False

if s[0] == 'A':
    a = 0
    flagA = True

# 文字列の両端から探索していきAのうち最左端にあるものZのうち最右端にあるものの要素数を記録　O(N/2)
i = 1
while not (flagA == True and flagZ == True):

    if s[i] == 'A' and flagA == False:
        a = i 
        flagA = True 
    if s[-i] == 'Z' and flagZ == False:
        z = len(s) - i
        flagZ = True
    
    i += 1
print(z-a+1)
import math as mt
a, b, c = map(int, input().split())
if a**2 + b**2 + 2*mt.sqrt(a*b) < c**2
  print("Yes")
else:
  print("No")


### FIXED CODE ###

import math as mt
a, b, c = map(int, input().split())
d = c - a - b
if d>0 and d**2 > 4*a*b:
  print("Yes")
else:
  print("No")
#  --*-coding:utf-8-*--

import math

def f(str):
    s = {}
    s[0] = 0
    pat = 0

    for c in str:
        pat ^= 2**(ord(c)-97)
        s[pat] = min(
            min(s.get(pat^2**i, math.inf) + 1 for i in range(26)),
            s.get(pat, math.inf))

    if pat == 0:
        return 1

    return s[pat]
            

def test():
    assert f('aabxyyzz') == 2
    assert f('byebye') == 1
    assert f('abcdefghijklmnopqrstuvwxyz') == 26
    assert f('abcabcxabcx') == 3


def main():
    str = input()
    print(f(str))


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def f(str):
    s = {}
    s[0] = 0
    pat = 0

    bits = [2**i for i in range(26)]
    lenOfStr = len(str)

    for c in str:
        pat ^= bits[ord(c)-97]
        s[pat] = min(
            min(s.get(pat^bit, lenOfStr) + 1 for bit in bits),
            s.get(pat, lenOfStr))

    if pat == 0:
        return 1

    return s[pat]
            
str = input()
print(f(str))
import math


def f(n):
    pop = 0
    ntemp = n
    for i in range(int(math.log2(n)) + 1):
        pop += ntemp % 2
        ntemp //= 2
    return n % pop


n = int(input())
S = input()
popcount = 0
for i in range(n):
    popcount += int(S[i])
Sint = int(S, 2)
remminus = Sint % (popcount - 1)
remplus = Sint % (popcount + 1)

# 1,2,4,...の余りのリストを準備
remlistminus = []
remlistplus = []
temp = 1
for i in range(n):
    remlistminus.append(temp)
    temp = (temp * 2) % (popcount - 1)
temp = 1
for i in range(n):
    remlistplus.append(temp)
    temp = (temp * 2) % (popcount + 1)
remlistminus.reverse()
remlistplus.reverse()

ans = []
for i in range(n):
    count = 1
    if S[i] == '0':
        rem = (remplus + remlistplus[i]) % (popcount + 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    else:
        rem = (remminus - remlistminus[i]) % (popcount - 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    ans.append(count)
for i in range(n):
    print(ans[i])


### FIXED CODE ###

import math


def f(n):
    pop = 0
    ntemp = n
    for i in range(int(math.log2(n)) + 1):
        pop += ntemp % 2
        ntemp //= 2
    return n % pop


n = int(input())
S = input()
popcount = 0
for i in range(n):
    popcount += int(S[i])

# 1が1個しかない場合の例外処理
if popcount == 1:
    if S[-1] == 1:
        ans = [2] * n
        ans[-1] = 0
    else:
        ans = [1] * n
        ans[-1] = 2
        for i in range(n):
            if S[i] == '1':
                ans[i] = 0
    for i in range(n):
        print(ans[i])
    exit()


Sint = int(S, 2)
remminus = Sint % (popcount - 1)
remplus = Sint % (popcount + 1)

# 1,2,4,...の余りのリストを準備
remlistminus = []
remlistplus = []
temp = 1
for i in range(n):
    remlistminus.append(temp)
    temp = (temp * 2) % (popcount - 1)
temp = 1
for i in range(n):
    remlistplus.append(temp)
    temp = (temp * 2) % (popcount + 1)
remlistminus.reverse()
remlistplus.reverse()

ans = []
for i in range(n):
    count = 1
    if S[i] == '0':
        rem = (remplus + remlistplus[i]) % (popcount + 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    else:
        rem = (remminus - remlistminus[i]) % (popcount - 1)
        while rem > 0:
            rem = f(rem)
            count += 1
    ans.append(count)
for i in range(n):
    print(ans[i])
input0=input("")
b=2
i=0

c=input0[::2]
d=input0[1::2]

for a in c:
    if(a=="L"):
        b=1
    else:
        b=0
    e=+b
    
for a in d:
    if(a=="R"):
        b=1
    else:
        b=0
    f=+b

g=e+f
if(g==0):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

input0=input("")
e=0
f=0
g=0
i=0

c=input0[::2]
d=input0[1::2]

for a in c:
    b=2
    if(a=="L"):
        b=1
    else:
        b=0
    e=e+b
    
for a in d:
    b=2
    if(a=="R"):
        b=1
    else:
        b=0
    f=f+b

g=e+f

if(g==0):
    print("Yes")
else:
    print("No")
n=int(input())
d={input();1for i in range(n)}
print(sum(d.values()))

### FIXED CODE ###

n=int(input())
d={input():1for i in range(n)}
print(sum(d.values()))
import math
a,b,c,d = map(int, input().split())
lcm = (c*d)//math.gcd(c,d)
print(lcm)
sum = b-a+1
x = (b//c) - ((a-1)//c)
y = (b//d) - ((a-1)//d)
z = (b//lcm) - ((a-1)//lcm)
n_i = x+y-z
print(int(sum-n_i))

### FIXED CODE ###

import fractions
a,b,c,d = map(int, input().split())
lcm = (c*d)//fractions.gcd(c,d)
sum = b-a+1
x = (b//c) - ((a-1)//c)
y = (b//d) - ((a-1)//d)
z = (b//lcm) - ((a-1)//lcm)
n_i = x+y-z
print(int(sum-n_i))
a,b=map(int,input().split())
s=0
g=0
if a==1:
  s=300000
elif a==2:
  s=200000
elif a==3:
  s=100000
else:
  pass
if b==1:
  g=300000
elif b==2:
  g=200000
elif b==3:
  g=100000
else:
  pass
if a=1 and b=2:
  print(300000+300000+400000)
else:
  print(s+g)

### FIXED CODE ###

a,b=map(int,input().split())
s=0
g=0
if a==1:
  s=300000
elif a==2:
  s=200000
elif a==3:
  s=100000
else:
  s=0
if b==1:
  g=300000
elif b==2:
  g=200000
elif b==3:
  g=100000
else:
  g=0
if a==1 and b==1:
  print(g+s+400000)
else:
  print(s+g)
a,b=[int(x) for x in input().split()]
  
  if(a*b==15):
    print("*")
  elif(a+b==15):
    print("+")
  else:
    print("x")
      

### FIXED CODE ###

a,b=[int(x) for x in input().split()]
  
if(a*b==15):
  print("*")
elif(a+b==15):
  print("+")
else:
  print("x")
import sys
import collections
n = int(input())
li=[input() for _ in range(n)]
c = collections.Counter(li)
max_list = [kv[0] for kv in c.items() if kv[1] == max(c.values())]
max_list.sort()
for s in max_list:
  print(s)

### FIXED CODE ###

import sys
li = list(map(int,input().split()))
li.sort()
if(str(li[0]) == str(li[1]) == str(li[2])):
  print("No")
  sys.exit()
if(str(li[0]) != str(li[1]) != str(li[2])):
  print("No")
  sys.exit()
for i in range(3):
  if(str(li[i]) == str(li[i+1])):
    print("Yes")
    break
x = input()
if x == ARC:
  print("ABC")
elif x == ABC:
  print("ARC")
else:
  print("invalid input")

### FIXED CODE ###

x = input()
def f(x):
    if x == "ABC":
        print("ARC")
    elif x == "ARC":
        print("ABC")
    else:
        print("invalid input")
f(x)
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    dp = [[0]*(m+2) for i in range(n+2)]
    sdp = [[0]*(m+2) for i in range(n+2)]
    dp[0][0] = 1
    sdp[1][1] = 1
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 and j == 0:continue
            if i>=1 and j >= 1 and s[i-1] == t[j-1]:
                dp[i][j] = sdp[i][j]%Mod
            sdp[i+1][j+1] = (sdp[i+1][j] + sdp[i][j+1] - sdp[i][j] + dp[i][j])%Mod

    print(sdp[n+1][m+1]%Mod)

if __name__ == "__main__":
    main() 
    
#endline===============================================
    

### FIXED CODE ###

X,A = map(int,input().split())
print(0 if X < A else 10)
import numpy
N, M = map(int, input().split())
dic = numpy.zeros([N,N], dtype = int)
for m in range(M):
    x, y = map(int, input().split())
    dic[x-1][y-1] = 1
mat = numpy.matrix(dic, int)
memo = numpy.zeros([N+1, N], dtype = int)
memo[0] = 1
z = numpy.zeros([N], int)
for n in range(N):
    memo[n+1] = (mat@(memo[n].reshape(-1,1))).reshape(4)
    if memo[n+1].any() == 0:
        print(ans)

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(100000)
 
N, M = map(int, input().split(" "))
G = [[] for _ in range(N)]
 
for _ in range(M):
    x, y = map(int, input().split(" "))
    G[x-1].append(y-1)
dp = [-1] * N
def pathlen(G, dp, v):
    if dp[v] != -1:
        return dp[v]
 
    plen = 0
    for i in G[v]:
        plen = max(plen, pathlen(G, dp, i)+1)
    dp[v] = plen
    return plen
ans = 0
for i in range(N):
    ans = max(ans, pathlen(G, dp, i))
print(ans)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.append()
B.append()
ans=0
for i in range(1,N+1):
	ans+=B[A[i-1]-1]
	if A[i-1]==A[i]-1:
		ans+=C[A[i-2]]
print(ans)

### FIXED CODE ###


N = int(input())
ans = 0
for i in range(N):
	for j in range(N):
		for t in range(N):
			ans+=1
print(ans)#N^3が答え
a=int(input().split())
s=input().split()
if a >= 3200:
  print(s)
else:
  print(a)

### FIXED CODE ###

a=int(input())
s=input()
if a >= 3200:
  print(s)
else:
  print('red')
H, W, K = map(int, raw_input().split())

MAP = [raw_input() for _ in xrange(H)]
dist = [[10000 for _ in range(W)] for _ in xrange(H)]

for i in range(H):
    x = MAP[i].find('S')
    if x != -1:
        sy = i
        sx = MAP[i].find('S')

Q = []
q(sx, sy)]
visited[sy][sx] = 0
while len(Q) > 0:
    x, y = Q.pop()
    d = visited[y][x]
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        px, py = x+dx, y+dy
        if px < 0 or px >= W:
            continue
        if py < 0 or py >= H:
            continue
        if abs(px - sx) + abs(py - sy) > K:
            continue
        if visited[py][px]:
            continue
        if MAP[py][px] == "#":
            continue
        Q.append((px, py))

d = 10000
for x in xrange(W):
    for y in xrange(H):
        if visited[y][x]:
            d = min(d, x, W-1-x)
            d = min(d, y, H-1-y)

if d == 0:
    print 1
elif d < K:
    print 2
else:
    print 1 + d/K


### FIXED CODE ###

from collections import deque

H, W, K = map(int, raw_input().split())

MAP = [raw_input() for _ in xrange(H)]
visited = [[False for _ in xrange(W)] for _ in xrange(H)]

for y in range(H):
    x = MAP[y].find('S')
    if x != -1:
        sx = x
        sy = y

Q = deque()
Q.append((0, (sx, sy)))
visited[sy][sx] = True
while len(Q) > 0:
    cost, [x, y] = Q.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        px, py = x+dx, y+dy
        if 0 <= px < W and 0 <= py < H:
            if not visited[py][px] and MAP[py][px] != "#":
                visited[py][px] = True
                if cost + 1 < K:
                    Q.append((cost + 1, (px, py)))

d = 10000
for x in xrange(W):
    for y in xrange(H):
        if visited[y][x]:
            d = min(d, x, W-1-x)
            d = min(d, y, H-1-y)

print (d + K - 1) / K + 1
A, B = map(int, input().split())
if A >= 13:
  print(B)
elif A <= 12 and A > 6:
  print(B//2)
else if A <= 5:
  print("0")

### FIXED CODE ###

A, B = map(int, input().split())
if A >= 13:
  print(B)
elif A <= 12 and A >= 6:
  print(B//2)
elif A <= 5:
  print("0")
x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
max_num = a[-1] + b[-1] + c[-1]
a_m = [aa - a[-1] for aa in a[:-1]]
b_m = [bb - b[-1] for bb in b[:-1]]
c_m = [cc - c[-1] for cc in c[:-1]]
d = a_m + b_m + c_m + [0]
d.sort()
d = list(reversed(d))
for i in range(k):
    ans = max_num + d[i]
    print(ans)

### 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)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
# -*- coding: utf-8 -*-
import numpy
A_ele = []
B_ele = []
ele = [int(x) for x in input().split()]
for i in range(ele[0]):
    A_ele.append([int(x) for x in input().split()])
A_ele = numpy.array(A_ele)
for i in range(ele[1]):
    B_ele.append([int(x) for x in input().split()])
B_ele = numpy.array(B_ele)
C_ele = A_ele.dot(B_ele)

for i in range(ele[0]):
    print(' '.join(map(str,C_ele[i])))


### FIXED CODE ###

# -*- coding: utf-8 -*-
A_ele = []
B_ele = []
C_ele = []
ele = [int(x) for x in input().split()]
for i in range(ele[0]):
    A_ele.append([int(x) for x in input().split()])
for i in range(ele[1]):
    B_ele.append([int(x) for x in input().split()])
for i in range(ele[0]):
    C_ele.append([])
    for j in range(ele[1]):
        for k in range(ele[2]):
            if j == 0:
                C_ele[i].append(0)
            C_ele[i][k] = C_ele[i][k] + A_ele[i][j] * B_ele[j][k]
for i in range(ele[0]):
    print(' '.join(map(str,C_ele[i])))
A = int(input())
B = int(input())
p = int(A + B)
m = int(A - B)
c = int(A * B)
s = [p,m,c]
max(s)

### FIXED CODE ###

A,B = list(map(int,input().split()))
p = int(A + B)
m = int(A - B)
c = int(A * B)
s = [p,m,c]
print(max(s))
A,B,C,D = [int(x) for x in input().split()]
print(min(A,B)+min(C,D))

### FIXED CODE ###

A,B,C,D = [int(input()) for _ in range(4)]
print(min(A,B)+min(C,D))
for i in range(n):
    b[i] = format(a[i], 'b').zfill(maxd)[::-1]
#print(b)

s = [0 for i in range(maxd)]
c = [0 for i in range(maxd)]
for i in range(maxd):
    c[i] = sum(list(map(lambda x: int(x[i]), b)))
for i in range(digitk1):
    for j in range(i):
        count = c[j]
        if count <= n/2:
            s[i] += (n - count) * 2 ** j
        else:
            s[i] += count * 2 ** j
    count = c[i]

    if int(bink[i]) == 0:
        s[i] = count * 2**i
        pass
    else:
        s[i] += count * 2 ** i

    for j in range(i+1, digitk):
        count = c[j]
        if int(bink[j]) == 0:
            s[i] += count * 2 ** j

        else:
            s[i] += (n-count) * 2 ** j

    for j in range(digitk1, maxd):
        count = c[j]
        s[i] += count * 2 ** j
print(max(s))

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = ['' for i in range(n)]
maxd = len(bin(10 ** 12 + 1))-2
bink = bin(k)[2:]
digitk = len(bink)
bink1 = bin(k+1)[2:]
digitk1 = len(bink1)
bink = bink.zfill(maxd)[::-1]
bink1 = bink1.zfill(maxd)[::-1]
for i in range(n):
    b[i] = format(a[i], 'b').zfill(maxd)[::-1]
#print(b)

s = [0 for i in range(maxd)]
c = [0 for i in range(maxd)]
for i in range(maxd):
    c[i] = sum(list(map(lambda x: int(x[i]), b)))
for i in range(digitk1):
    if bink1[i] == '1':
        for j in range(i):
            if c[j] <= n/2:
                s[i] += (n-c[j]) * 2 ** j
            else:
                s[i] += c[j] * 2 ** j

        s[i] += c[i] * 2 ** i

        for j in range(i+1, digitk1):
            if bink1[j] == '1':
                s[i] += (n-c[j]) * 2 ** j
            else:
                s[i] += c[j] * 2 ** j

    for j in range(digitk1, maxd):
        s[i] += c[j] * 2 ** j
print(max(s))
def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))
    C = tuple(map(int, input().split()))

    b = [0] * 100002
    for i in B:
        b[i] += 1

    cnt = 0
    for i in A:
        for j in C:
            if i < j:
                cnt += sum(b[i+1:j])

    print(cnt)

main()


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))
    C = tuple(map(int, input().split()))

    a = sorted(A)
    c = sorted(C)
    cnt = 0
    for i in B:
        x = bisect.bisect_left(a, i)
        y = bisect.bisect_right(c, i)
        cnt += x * (N - y)

    print(cnt)

main()
#coding:utf-8
s=[int(i) for i in input().split()]
n=[]
for i in range(s[0]):
  n.append(int(input()))
n.sort()
sa=abs(n[0]-n[s[1]]-1)
for i in range(s[1]-1):
  if(sa>abs(n[i]-n[i+s[1]-1])):
    sa=abs(n[i]-n[i+s[1]-1])
print(sa)

### FIXED CODE ###

n=[int(i) for i in input().split()]
array=[]
for i in range(n[0]):
  array.append(int(input()))
array.sort()
ans=abs(array[0]-array[n[1]-1])
for i in range(n[0]-(n[1]-1)):
  if(ans>abs(array[i]-array[i+n[1]-1])):
    ans=abs(array[i]-array[i+n[1]-1])
print(ans)
def cmb(n,r):
        if r > n: 
            return 0
        if n - r < r:
             r = n - r
        if r > n: 
            return 0
        if r == 0: 
            return 1
        if r == 1: 
            return n
    
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
    
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
    
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
    
        return resultr


import collections
N = int(input())
s= [input() for i in range(N)]
ans=0
#各文字列文字列をソート
s=list(map(sorted,s))

s.sort()        #リストをソート
s=list(map(''.join,s))  #リストになっていたものを文字列に変換
clist = collections.Counter(s) #リスト内の各要素の数を数え上げ
kaisu=list(clist.values())

for i in kaisu:
        ans += cmb(i,2)

print(ans)


### FIXED CODE ###

import math
def cmb(n, r):
        if r > n: 
                return 0
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


import collections
N = int(input())
s= [input() for i in range(N)]
ans=0
#各文字列文字列をソート
s=list(map(sorted,s))

s.sort()        #リストをソート
s=list(map(''.join,s))  #リストになっていたものを文字列に変換
clist = collections.Counter(s) #リスト内の各要素の数を数え上げ
kaisu=list(clist.values())

for i in kaisu:
        ans += cmb(i,2)

print(ans)
import sys
j = [int(a)**2 + int(b)**2 - int(c)**2 for line in sys.stdin for a,b,c in line.split(",")]
print(len([i for i in j if not i]))
print(len([i for i in j if i]))

### FIXED CODE ###

import sys
t, h = 0, 0
for line in sys.stdin:
    try:
        a, b, c = line.split(",")
        if not int(a) ** 2 + int(b) ** 2 - int(c) ** 2:
            t += 1
        elif int(a) == int(b):
            h += 1
    except:
        break
print(t)
print(h)
from functools import*
@lru_cache
def d(n):x=n//2;return n+1 if n<2 else d(x)+d(~-x)+d(n+~x)
print(d(int(input()))%(10**9+7))

### FIXED CODE ###

from functools import*
@lru_cache(maxsize=None)
def d(n):x=n//2;return n+1 if n<2 else d(x)+d(~-x)+d(n+~x)
print(d(int(input()))%(10**9+7))
while 1:
  H, W = map(int, raw_input().split())
  if (H == 0 and W == 0):
    break
 
      print ('#' * W)
      for i in range(H-2):
        print ('#' + '.' * (W - 2) + '#' )
      print ('#'* W)
  print" "
 

### FIXED CODE ###

while 1:
  H, W = map(int, raw_input().split())
  if (H == 0 and W == 0):
    break
 
  print ('#' * W)
  for i in range(1,H-1):
    print ('#' + '.' * (W - 2) + '#' )
  print ('#'* W)
  print""
n = input()
int_list = list(map(int, input().split()))
count = 0
while True:
    isOdd = False
    for i in range(n):
        if(int_list[i] % 2 != 0):
            isOdd = True
    if isOdd:
        break
    for i in range(n):
        int_list[i] = int_list[i]/2
    count = count + 1

print(count)


### FIXED CODE ###

str_list = input()
count = 0
if str_list[0] == '1':
  count = count + 1
if str_list[1] == '1':
  count = count + 1
if str_list[2] == '1':
  count = count + 1
print(count)
dic = {}
dic['A'] = 'T'
dic['T'] = 'A'
dic['C'] = 'G'
dic['G'] = 'C'

def a(b):
	return dic[b]

a=input()
print(a(a))


### FIXED CODE ###

dic = {}
dic['A'] = 'T'
dic['T'] = 'A'
dic['C'] = 'G'
dic['G'] = 'C'

def C(b):
    return dic[b]

a=input()
print(C(a))
a=input()
if a[0]=="1":
  a[0]="9"
if a[0]=="9":
  a[0]=="1"
if a[1]=="1":
  a[1]=="9"
if a[1]=="9":
  a[1]=="1"
if a[2]=="1":
  a[2]=="9"
if a[2]=="9":
  a[2]=="1"
print(a)

### FIXED CODE ###

a=input()
print(a.replace("1","8").replace("9","1").replace("8","9"))
n, x = map(int, input().split())
xi = list(map(int, input().split()))

import math
import fraction
from functools import reduce

def gcd(*numbers):
    return reduce(fraction.gcd, numbers)

xi = map(lambda y:y-x, xi)
print(gcd(*xi))

### FIXED CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcd_l(*numbers):
	ret = numbers[0]
	for n in numbers[1:]:
		ret = gcd(ret, n)
	return ret

xi = map(lambda y:abs(y-x), xi)
print(gcd_l(*xi))