Jim runs a big burger restaurant and, to entertain his customers, he always tell them jokes. He is running out of jokes and he needs you to help him find new ones.

An often heard programmer joke goes like this:

"Why do programmers always mix up Christmas and Halloween? Because Dec 25 is Oct 31".

Got it? :-) It is because $25_{10}$ (25 in Decimal) is equal to ${31}_{8}$ (31 in Octal).

If we are talking about dates, then let $m$ be the month and ${d}$ be the date and the corresponding value be $f(m,d)=d_m$ (${d}$ in base $m$). Let's describe some slightly different jokes:

"Why do programmers always mix up event $\boldsymbol{x}$ and event $y$? Because $f(m_x,d_x)=f(m_y,d_y)$". 

Here $m_{x}$ means the month of event ${x}$ and $d_x$ the day of event ${x}$. Similar for $m_y$ and $d_y$.  

Jim knows that his customers love this kind of jokes. That's why he gives you a calendar with $N$ events in it and asks you to count the number of such jokes he can create using the given events.

Two jokes ($(x_1,x_2)$ and $(y_{1},y_{2})$) differ if they don't contain the same events.

Note: 

The given numbers are all represented with digits from 0-9, that's why for months like ${11}$ or $12$, we can't use additional characters to represent 10 or 11. 

It might happen, that a special event cannot be used for a joke because the base conversion is invalid. For example $25_2$ is not possible since base $2$ can only contain digits ${0}$ and ${1}$.  

Unary base is invalid.  

Two events can have the same date.

Input Format

On the first line you will get $N$. The following $N$ lines you will be given the dates $m_i$, $d_i$ of the special events, each separated by a single space. 

Output Format

Print the number of jokes Jim can make.

Constraints 

$1\leq N\leq10^5$
($m_i$, $d_i$) will be a valid date in the Gregorian Calendar without leap day. 

Sample Input #1

2
10 25
8 31

Sample Output #1

1

Sample Input #2

2
2 25
2 25

Sample Output #2

0

Sample Input #3

2
11 10
10 11

Sample Output #3

1

Explanation

There are two special events happening on $(10,25)$ and $(8,31)$. He can make one joke, namely the one described in the description.

In the second test case there are no valid dates we can use for our jokes since 25 is not defined for base 2.

In the third test case $f(11,10)=10_{11}=11_{10}=f(10,11)$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Mathematics


Solutions:
def decode(b, x):
	try:
		return int(str(x), b)
	except:
		return None
cnt = {}
n = int(input())
for _ in range(n):
	(b, x) = map(int, input().split())
	val = decode(b, x)
	if val != None:
		cnt[val] = cnt.get(val, 0) + 1
ans = sum((x * (x - 1) // 2 for x in cnt.values()))
print(ans)


def is_valid(b, n):
	for i in n:
		if i >= b:
			return False
	return True

def to_dec(b, n):
	if not is_valid(b, n):
		return None
	res = 0
	for (i, nn) in enumerate(reversed(n)):
		res += nn * b ** i
	return res
n = int(input())
dates = []
for _ in range(n):
	(b, n) = input().split()
	dates.append([int(b), [int(x) for x in list(n)]])
same = {}
for x in dates:
	v = to_dec(x[0], x[1])
	if v:
		if v not in same:
			same[v] = 1
		else:
			same[v] += 1
tot = 0
for k in same:
	tot += same[k] * (same[k] - 1) / 2
print(int(tot))


def date_valid(date):
	base = date[0]
	day = str(date[1])
	for num in day:
		if int(num) >= base:
			return False
	return True

def convert_date(date):
	base = date[0]
	day = str(date[1])
	event = 0
	for i in range(len(day)):
		event += base ** (len(day) - i - 1) * int(day[i])
	return event
N = int(input())
dates = []
for i in range(N):
	dates.append(list(map(int, input().split(' '))))
valid_dates = []
for date in dates:
	if date_valid(date):
		valid_dates.append(date)
converted_dates = []
count = 0
pairs = 0
current = -1
for valid_date in valid_dates:
	converted_date = convert_date(valid_date)
	converted_dates.append(converted_date)
converted_dates = sorted(converted_dates)
for i in range(len(converted_dates)):
	if i == 0:
		count += 1
	elif converted_dates[i] == converted_dates[i - 1]:
		count += 1
	else:
		pairs += int(count * (count - 1) / 2)
		count = 1
if count != 1:
	pairs += int(count * (count - 1) / 2)
print(pairs)


from collections import defaultdict
t = int(input())
dates = defaultdict(int)
for _ in range(t):
	(base, value) = input().split()
	try:
		dates[int(value, int(base))] += 1
	except ValueError:
		continue
count = 0
for c in dates.values():
	count += c * (c - 1) // 2
print(count)


def decode(b, x):
	try:
		return int(str(x), b)
	except:
		return None
cnt = {}
for _ in range(int(input())):
	(b, x) = map(int, input().split())
	val = decode(b, x)
	if val != None:
		cnt[val] = cnt.get(val, 0) + 1
print(sum((x * (x - 1) // 2 for x in cnt.values())))


d = 38 * [0]
n = int(input())
jokes = 0
while n > 0:
	(b, a) = input().split()
	b = int(b)
	a = int(a)
	if a % 10 < b and a // 10 < b:
		i = a // 10 * b + a % 10
		d[i] += 1
	n -= 1
for i in range(0, 38):
	if d[i] > 1:
		jokes += d[i] * (d[i] - 1) // 2
print(jokes)


T = int(input())
from collections import Counter
c = Counter()
for t in range(T):
	(m, d) = input().split()
	try:
		c[int(d, int(m))] += 1
	except:
		pass
print(sum(((n - 1) * n // 2 for n in c.values())))


n = int(input())
a = []
for _ in range(n):
	(m, d) = input().split()
	try:
		a.append(int(d, int(m)))
	except:
		continue
count = {}
for i in a:
	if i in count:
		count[i] += 1
	else:
		count[i] = 1
result = 0
for (key, value) in count.items():
	if value > 1:
		jokes = 0
		while value >= 1:
			jokes += value - 1
			value -= 1
		result += jokes
print(result)


eventCount = int(input())
inputEvents = [input().split(' ') for i in range(eventCount)]
events = []
for event in inputEvents:
	events.append(event)
events = [int(i[1], int(i[0])) for i in events if int(i[0]) > 1 and max([int(j) for j in i[1]]) < int(i[0])]
eventHash = {}
for event in events:
	if event in eventHash:
		eventHash[event] += 1
	else:
		eventHash[event] = 1
eventCount = sum([int(i * (i - 1) / 2) for i in eventHash.values()])
print(str(eventCount))


from itertools import groupby
T = int(input())
A = []
for _ in range(T):
	(x, y) = [x for x in input().split()]
	try:
		N = int(y, int(x))
		A.append(N)
	except:
		pass
A.sort()
Result = 0
for i in [len(list(group)) for (key, group) in groupby(A)]:
	Result += i * (i - 1) // 2
print(Result)


import collections, sys
N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
c = collections.Counter((int(str(d), m) for (m, d) in A if all((int(c) < m for c in str(d)))))
print(sum((x * (x - 1) // 2 for x in c.values())))


import math

def normalize(m, d):
	result = 0
	power = 0
	while d:
		digit = d % 10
		if digit < m:
			result += digit * m ** power
		else:
			return -1
		d //= 10
		power += 1
	return result

def comb(n, r):
	if n < r:
		return 0
	return math.factorial(n) // math.factorial(n - 2) // 2
dates = []
for _ in range(int(input())):
	(m, d) = map(int, input().split())
	date = normalize(m, d)
	if date > 0:
		dates.append(date)
dates.sort()
last_date = -1
count = 0
result = 0
for date in dates:
	if date == last_date:
		count += 1
	else:
		result += comb(count + 1, 2)
		count = 0
	last_date = date
result += comb(count + 1, 2)
print(result)


def toint(m, d):
	try:
		return int(d, int(m))
	except:
		pass
nums = {}
result = 0
n = int(input())
for i in range(n):
	(m, d) = input().split()
	num = toint(m, d)
	if num != None:
		if num in nums:
			result += nums[num]
			nums[num] += 1
		else:
			nums[num] = 1
print(result)


counts = [0] * 38
for _ in range(int(input())):
	(month, day) = input().split()
	try:
		counts[int(day, int(month))] += 1
	except ValueError:
		pass
print(sum((n * (n - 1) // 2 for n in counts)))


import sys

def to_dec(a, b):
	ln = len(a)
	for i in range(0, ln):
		if int(a[i]) >= b:
			return -1
	mn = 1
	sm = 0
	for i in range(ln - 1, -1, -1):
		sm += int(a[i]) * mn
		mn *= b
	return sm
cnt = []
val = []
size = 0
n = sys.stdin.readline()
n = int(n)
ans = 0
for i in range(0, n):
	(a, b) = sys.stdin.readline().split()
	a = int(a)
	v = to_dec(b, a)
	if v == -1:
		continue
	fn = False
	for j in range(0, size):
		if val[j] == v:
			fn = True
			cnt[j] += 1
			break
	if fn == False:
		val.append(v)
		cnt.append(1)
		size += 1
for i in range(0, size):
	ans += cnt[i] * (cnt[i] - 1) >> 1
print(ans)


from collections import Counter

def modBinomial(n, k):
	numerator = 1
	for i in range(k):
		numerator = numerator * (n - i)
	denominator = 1
	for i in range(1, k + 1):
		denominator = denominator * i
	return numerator // denominator
n = []
for _ in range(int(input())):
	(m, d) = [int(ns) for ns in str(input()).split()]
	if m > 1:
		ds = [int(x) for x in str(d)]
		ds = reversed(ds)
		nn = 0
		i = 0
		for x in ds:
			if x >= m:
				nn = -1
				break
			nn += x * m ** i
			i += 1
		if nn > -1:
			n.append(nn)
C = Counter(n)
print(sum((modBinomial(C[c], 2) for c in C if C[c] > 1)))


from collections import Counter
n_events = int(input())
events = []
for n in range(n_events):
	(m, d) = input().split()
	try:
		events.append(int(d, int(m)))
	except ValueError:
		pass
event_count = Counter(events)
print(sum((x * (x - 1) // 2 for x in event_count.values())))


import collections, math
n = int(input().strip())
d = collections.Counter()
for a0 in range(n):
	(m0, d0) = input().strip().split(' ')
	m0 = int(m0)
	d01 = int(d0)
	if m0 == 1:
		continue
	else:
		try:
			d0 = int(d0, base=m0)
		except:
			continue
	d[d0] += 1
c = 0
for x in d:
	if d[x] == 2:
		c += 1
	elif d[x] == 1:
		continue
	else:
		combinations = int(math.factorial(d[x]) / (math.factorial(2) * math.factorial(d[x] - 2)))
		c += combinations
print(c)


from collections import defaultdict

def isLegit(m, d):
	if m == 1:
		return False
	for j in str(d):
		if int(j) >= m:
			return False
	return True

def fromBase(m, d):
	if isLegit(m, d):
		a = str(d)
		s = 0
		for i in range(len(a)):
			s += int(a[-i - 1]) * m ** i
		return s
	else:
		return -1
t = 0
cases = defaultdict(list)
N = int(input())
for _ in range(N):
	(m, d) = [int(x) for x in input().split()]
	k = fromBase(m, d)
	if k != -1:
		cases[k] += [[m, d]]
		t += len(cases[k]) - 1
print(t)


dates = list((tuple(input().split()) for _ in range(int(input()))))
D = {}
for (month, day) in dates:
	try:
		f = int(day, int(month))
		D[f] = D.get(f, 0) + 1
	except:
		pass
s = 0
for d in D:
	s += (D[d] - 1) * D[d] // 2
print(s)


def base2dec(base, num):
	retval = 0
	upper_digit = num // 10
	retval += base * upper_digit + num - upper_digit * 10
	return retval
n = int(input().strip())
cal_lst = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
calendar = []
for i in range(n):
	dl = input().strip().split()
	(m, d) = [int(dl[0]), int(dl[1])]
	if m > d - d // 10 * 10 and m > d // 10:
		if d <= cal_lst[m - 1]:
			calendar.append([m, d])
evs = []
for i in calendar:
	evs.append(base2dec(i[0], i[1]))
sorted_evs = sorted(evs)
base = 0
compare = 0
cases = []
total = 0
val = 0
while base < len(sorted_evs) and compare < len(sorted_evs):
	if sorted_evs[base] == sorted_evs[compare]:
		val += 1
		compare += 1
	else:
		base = compare
		cases.append(val)
		val = 0
cases.append(val)
for case in cases:
	total += case * (case - 1) / 2
print(int(total))


from collections import Counter

def convert_to_base10(n, base):
	digits = [int(x) for x in str(n)]
	if base == 1 or any((base <= digit for digit in set(digits))):
		return False
	val = 0
	power = 0
	for digit in digits[::-1]:
		val += digit * base ** power
		power += 1
	return val
counter = Counter()
possible_jokes = 0
t = int(input())
for _ in range(t):
	(m, d) = [int(x) for x in input().split()]
	x = convert_to_base10(d, m)
	if x:
		counter[x] += 1
for n in counter.values():
	if n > 1:
		if n % 2 == 0:
			possible_jokes += n // 2 * (n - 1)
		else:
			possible_jokes += n * ((n - 1) // 2)
print(possible_jokes)


import math
from collections import Counter

def get_num_equal_dates(dates):
	converted_dates = []
	for (d, m) in dates:
		try:
			converted_dates.append(int(d, m))
		except ValueError:
			pass
	joke_dates = [c for (_, c) in Counter(converted_dates).items() if c >= 2]
	combinations = lambda n: n * (n - 1) // 2
	return sum(map(combinations, joke_dates))
n = int(input())
dates = []
for _ in range(n):
	(m, d) = input().split()
	dates.append((d, int(m)))
print(get_num_equal_dates(dates))


import sys
n = 0
line = 0
j = []
for text in sys.stdin:
	if line > 0:
		m = int(text.split()[0])
		d = int(text.split()[1])
		if m > 1:
			d = str(d)
			if len(d) == 1:
				if int(d) < m:
					n += 1
					j.append(int(d))
			elif len(d) == 2:
				if int(d[0]) < m and int(d[1]) < m:
					n += 1
					j.append(int(d[0]) * m + int(d[1]))
	line += 1
bins = list(set(j))
hist = {}
for b in bins:
	hist[b] = 0
for b in j:
	hist[b] += 1
total = 0
for b in bins:
	if hist[b] > 1:
		total += int(hist[b] * (hist[b] - 1) / 2)
print(total)


n = int(input())
dates = []
for i in range(n):
	(m, d) = [int(x) for x in input().split()]
	d1 = d % 10
	d2 = d // 10
	if max(d1, d2) < m:
		dates.append([m, d, d1 + d2 * m])
punchlines = {date[2] for date in dates}
jokes = 0
for punchline in punchlines:
	num = len([date for date in dates if date[2] == punchline])
	jokes += num * (num - 1) // 2
print(jokes)


vals = {}
for xx in range(int(input())):
	(m, d) = map(int, input().split())
	val = 0
	ok = True
	mult = 1
	while d:
		x = d % 10
		d = d // 10
		if x >= m:
			ok = False
			break
		else:
			val += x * mult
		mult *= m
	if not ok:
		continue
	vals.setdefault(val, 0)
	vals[val] += 1
ans = 0
for x in vals.values():
	ans += x * (x - 1) // 2
print(ans)


def baseify(m, d):
	if max(d // 10, d % 10) >= m:
		return -1
	return d // 10 * m + d % 10
n = int(input().strip())
dates = [-1] * n
for i in range(n):
	(m, d) = [int(i) for i in input().strip().split()]
	dates[i] = baseify(m, d)
dates = [i for i in dates if i != -1]
vals = list(set(dates))
total = 0
for i in vals:
	k = dates.count(i)
	total += k * (k - 1) // 2
print(total)


from collections import defaultdict
D = []

def solve(ds):
	dd = defaultdict(int)
	for (m, d) in ds:
		mi = int(m)
		if all([int(c) < mi for c in d]):
			k = int(d, mi)
			dd[k] += 1
	acc = 0
	for (k, v) in dd.items():
		acc += v * (v - 1) // 2
	return acc
for _ in range(int(input())):
	(m, d) = input().strip().split()
	D.append((m, d))
print(solve(D))


def changebase(num, base):
	ans = ''
	while num != 0:
		rem = num % base
		if rem > 9:
			return 0
		ans = str(rem) + ans
		num //= base
	return int(ans)

def base10(num, base):
	ans = 0
	num = str(num)
	for i in range(len(num)):
		ans *= base
		ans += int(num[i])
	return ans

def checkvalid(num, base):
	num = str(num)
	for x in num:
		if int(x) >= base:
			return False
	return True
ans = 0
dates = dict()
for _ in range(int(input())):
	(base, number) = tuple(map(int, input().split()))
	if not checkvalid(number, base) or base == 1:
		continue
	num10 = base10(number, base)
	ans += dates.get((10, num10), 0)
	for i in range(2, 10):
		ans += dates.get((i, changebase(num10, i)), 0)
	for i in range(11, 13):
		ans += dates.get((i, changebase(num10, i)), 0)
	if (base, number) in dates:
		dates[base, number] += 1
	else:
		dates[base, number] = 1
print(ans)


from collections import defaultdict

def fa(m, n):
	a = 1
	for i in range(m, n + 1):
		a *= i
	return a

def C(n, r):
	return fa(n - r + 1, n) // fa(1, r)

def f(m, d):
	if m == 1:
		return -1
	a = 0
	d = str(d)
	ind = len(d) - 1
	for i in d:
		i = int(i)
		if i >= m:
			return -1
		a += i * m ** ind
		ind -= 1
	return a
dic = defaultdict(int)
n = int(input())
for i in range(n):
	(m, d) = [int(x) for x in input().split()]
	a = f(m, d)
	if a != -1:
		dic[a] += 1
ans = 0
for i in dic:
	ans += C(dic[i], 2)
print(ans)


counts = [0] * 38
for _ in range(int(input())):
	(m, d) = input().split()
	try:
		x = int(d, int(m))
	except ValueError:
		pass
	else:
		counts[x] += 1
print(sum((x * (x - 1) // 2 for x in counts if x)))


n = int(input())
arr = []
for i in range(n):
	arrtemp = input().split(' ')
	base = int(arrtemp[0])
	if base != 1:
		decnum = 0
		flag = False
		for j in range(len(arrtemp[1])):
			if int(arrtemp[1][j]) < base:
				decnum += int(arrtemp[1][j]) * base ** (len(arrtemp[1]) - 1 - j)
			else:
				flag = True
				break
		if not flag:
			arr.append(decnum)
jokes = 0
for d in set(arr):
	num = arr.count(d)
	jokes += num * (num - 1) // 2
print(jokes)


from collections import Counter
events = []
for _ in range(int(input())):
	try:
		(b, d) = input().split()
		events.append(int(d, int(b)))
	except ValueError:
		continue
print(sum((count * (count - 1) // 2 for count in Counter(events).values())))


from collections import Counter
from sys import stdin
filou = None
if filou:
	rd = open(filou, 'r')
else:
	rd = stdin
entree = rd.read(10000000)

def cnv(lg):
	(M, D) = list(map(int, lg.split()))
	(d, u) = divmod(D, 10)
	if M == 1 or max(d, u) >= M:
		return 0
	return u + d * M
lin = Counter(list(entree.splitlines())[1:])
autre = Counter()
for pv in lin.items():
	autre[cnv(pv[0])] += pv[1]
del autre[0]
print(sum(((n ** 2 - n) // 2 for n in autre.values())))


N = int(input())
datedict = {}
for i in range(0, N):
	(m, d) = input().split()
	m = int(m)
	datnum = 0
	multiplier = 1
	valid = True
	for l in range(0, len(d)):
		thisChar = int(d[-l - 1])
		if thisChar >= m:
			valid = False
		datnum += thisChar * multiplier
		multiplier *= m
	if valid:
		datedict[datnum] = datedict.get(datnum, 0) + 1
jokes = 0
for i in datedict:
	thisCount = datedict[i]
	jokes += thisCount * (thisCount - 1) // 2
print(jokes)


from collections import defaultdict
ans = 0
d = defaultdict(list)
for _ in range(int(input())):
	(m_x, d_x) = input().strip().split()
	m_x = int(m_x)
	if all([int(d) < m_x for d in d_x]):
		d[int(d_x, m_x)].append((m_x, d_x))
for (k, s) in d.items():
	ans += len(s) * (len(s) - 1) / 2
print(int(ans))


def convertDec(b, n):
	if b == 10:
		return n
	if b == 1:
		return -1
	p = 0
	d = 0
	q = 1
	while n > 0:
		if n % 10 >= b:
			return -1
		p += q * (n % 10)
		n = n // 10
		q *= b
		d += 1
	return p
n = int(input())
m = {}
c = 0
for i in range(n):
	(x, y) = map(int, input().split())
	z = convertDec(x, y)
	if z < 0:
		continue
	if z in m:
		m[z] += 1
	else:
		m[z] = 1
for x in m:
	n = m[x]
	c += n * (n - 1) // 2
print(c)


n = int(input())
ar = []
for _ in range(n):
	(base, val) = map(int, input().split())
	try:
		ar.append(int(str(val), base))
	except:
		pass
ar.sort()
q = [1]
for i in range(len(ar) - 1):
	if ar[i] == ar[i + 1]:
		q[-1] += 1
	else:
		q.append(1)
ans = 0
for x in q:
	if x == 1:
		continue
	else:
		ans += x * (x - 1) // 2
print(ans)


n = int(input())
arr = [0] * 38
while n:
	n -= 1
	(m, d) = (x for x in input().split(' '))
	m = int(m)
	add = True
	for c in d:
		if int(c) >= m:
			add = False
			break
	if add:
		val = 0
		for c in d:
			val *= m
			val += int(c)
		arr[val] += 1
s = 0
for i in arr[1:]:
	if i > 1:
		s += i * (i - 1) // 2
print(s)


import datetime

def convert_date(m, d):
	d = list(str(d))
	d.reverse()
	date_digits = list(map(int, d))
	if all(map(lambda x: x < m, date_digits)):
		return sum([date_digits[idx] * m ** idx for idx in range(len(date_digits))])
	return -1
in_dates = list([])
for n_trials in range(int(input())):
	(m, d) = map(int, input().split())
	try:
		datetime.datetime(2001, m, d)
	except ValueError:
		pass
	else:
		val = convert_date(m, d)
		if val > 0:
			in_dates.append(val)
total_events = 0
while len(in_dates) > 1:
	key_val = in_dates[0]
	count = sum([1 for val in in_dates if val == key_val])
	total_events += count * (count - 1) / 2
	in_dates = [val for val in in_dates if val != key_val]
print('{}'.format(int(total_events)))


from collections import Counter
c = Counter()
for _ in range(int(input())):
	(m, d) = input().split()
	try:
		c[int(d, int(m))] += 1
	except ValueError:
		pass
print(sum((n * (n - 1) // 2 for n in c.values())))


def f(b, n):
	s = str(n)
	k = len(s)
	if max([int(i) for i in s]) >= b or b < 2:
		return -1
	return sum((int(s[k - 1 - i]) * b ** i for i in range(k)))
T = int(input())
S = {}
for t in range(T):
	(b, n) = [int(i) for i in input().split()]
	a = f(b, n)
	if a >= 0:
		if a in S:
			S[a] += 1
		else:
			S[a] = 1
print(sum((i * (i - 1) // 2 for i in S.values() if i > 1)))


from collections import defaultdict
counter = defaultdict(int)
for _ in range(int(input())):
	(m, d) = input().split()
	(m, date) = (int(m), 0)
	for i in map(int, d):
		if m > i:
			date = date * m + i
		else:
			break
	else:
		counter[date] += 1
print(sum((n * (n - 1) // 2 for n in counter.values())))


events = [0] * 40
N = int(input())
for _ in range(N):
	(m, d) = input().split()
	try:
		i = int(d, int(m))
		events[i] += 1
	except:
		pass
jokes = 0
for n in events:
	jokes += n * (n - 1) // 2
print(jokes)


dict = {}
c = 0
for i0 in range(int(input())):
	(m, d) = input().strip().split()
	(m, d) = (int(m), int(d))
	try:
		x = int(str(d), m)
	except ValueError:
		continue
	if x in dict.keys():
		dict[x] += 1
	else:
		dict[x] = 1
for b in dict.values():
	c += sum(range(b))
print(c)


N = int(input())
A = []
for n0 in range(N):
	(m, d) = [int(a) for a in input().split()]
	s = 0
	valid = True
	d = str(d)
	for i in range(len(d)):
		if int(d[i]) >= m:
			valid = False
			break
		s += int(d[i]) * m ** (len(d) - 1 - i)
	if not valid:
		continue
	A.append(s)
j = 0
for a in set(A):
	j += A.count(a) * (A.count(a) - 1) // 2
print(j)


def g(x, y):
	e = y % 10
	d = y // 10
	if d >= x or e >= x:
		return None
	return e + x * d

def check_class(md, k):
	s = len(md[k]) * (len(md[k]) - 1) // 2
	return s
md = {}
N = int(input())
for i in range(N):
	(m, d) = (int(j) for j in input().split())
	k = g(m, d)
	if k == None:
		continue
	if k not in md:
		md[k] = [(m, d)]
	else:
		md[k].append((m, d))
s = 0
for i in md:
	s += check_class(md, i)
print(s)


dates = []
for date in range(int(input())):
	dates.append(input().split(' '))
rem = []
for date in dates:
	date[0] = int(date[0])
	date[1] = [int(char) for char in date[1]]
	if (date[0] == 1) | (max(date[1]) >= date[0]):
		date[1] = -1
	else:
		date[1] = sum([date[1][-i - 1] * date[0] ** i for i in range(len(date[1]))])
unique = set((date[1] for date in dates))
counts = [sum((1 for date in dates if date[1] == day)) for day in unique if day != -1]
print(sum((n * (n - 1) // 2 for n in counts)))


N = int(input())
counts = [0] * 38
for n in range(N):
	(m, d) = input().split()
	m = int(m)
	v = 0
	for c in d:
		k = int(c)
		if k < m:
			v = m * v + k
		else:
			break
	else:
		counts[v] += 1
res = sum((count * (count - 1) // 2 for count in counts))
print(res)


N = int(input().strip())
ans = {}
for _ in range(N):
	(m, d) = list(map(int, input().strip().split()))
	try:
		x = int(str(d), m)
		if x in ans:
			ans[x] += 1
		else:
			ans[x] = 1
	except ValueError:
		pass
total = sum((x * (x - 1) // 2 for x in ans.values()))
print(total)


def illegal_chars(b):
	return [str(a) for a in range(b, 10)]
count = 0
values = [0] * 37
N = int(input())
for i in range(N):
	s = input().split()
	base = int(s[0])
	if base >= 2 and (not any((c in s[1] for c in illegal_chars(base)))):
		v = int(s[1], base)
		values[v - 1] += 1
for val in values:
	count += val * (val - 1) // 2
print(count)


def to_dec(n, b):
	(result, place) = (0, 0)
	while n:
		digit = n % 10
		if digit >= b:
			return 0
		result += digit * b ** place
		n //= 10
		place += 1
	return result

def triangular_number(n):
	return n * (n + 1) // 2
N = int(input())
A = {}
for _ in range(N):
	(m, d) = [int(x) for x in input().strip().split(' ')]
	r = to_dec(d, m)
	if r in A.keys():
		A[r] += 1
	elif r != 0:
		A[r] = 0
print(sum([triangular_number(y) for (x, y) in A.items() if y > 0]))


L = []
for _ in range(int(input())):
	(m, d) = [int(i) for i in input().split()]
	if 1 <= m and m <= 12 and (1 <= d) and (m == 2 and d <= 28 or (m in [4, 6, 9, 11] and d <= 30) or (m in [1, 3, 5, 7, 8, 10, 12] and d <= 31)):
		try:
			L.append(int(str(d), base=m))
		except ValueError as e:
			pass
L.sort()
complete = lambda x: x * (x - 1) // 2
sum = 0
if L:
	prev = L[0]
	count = 1
	for now in L[1:]:
		if now == prev:
			count += 1
		else:
			sum += complete(count)
			prev = now
			count = 1
	sum += complete(count)
print(sum)


n = int(input())
H = {}
for _ in range(n):
	(a, b) = input().split()
	try:
		x = int(b, int(a))
		if x not in H:
			H[x] = 0
		H[x] += 1
	except:
		pass
print(sum((x * (x - 1) // 2 for x in H.values())))


N = int(input())
eventcounts = {}
for n in range(N):
	(mi, di) = input().split()
	m = int(mi)
	if m != 1:
		d = int(di)
		try:
			f = int(di, base=m)
		except ValueError:
			pass
		else:
			if not f in eventcounts:
				eventcounts[f] = 0
			eventcounts[f] += 1
jokecount = 0
for eventcount in eventcounts.values():
	if eventcount > 1:
		jokecount += eventcount * (eventcount - 1) // 2
print(jokecount)


from math import factorial as fa

def ncr2(n):
	return fa(n) // 2 // fa(n - 2)
jokes = {}
for _ in range(int(input().strip())):
	(m, d) = input().strip().split(' ')
	try:
		j = int(d, base=int(m))
		jokes[j] = jokes.get(j, 0) + 1
	except ValueError:
		pass
print(sum((ncr2(n) for n in jokes.values() if n > 1)))


from collections import defaultdict

def isCorrBase(d, m):
	return all([0 <= int(c) and int(c) < m for c in d])

def toBase(d, m):
	if len(d) == 1:
		return int(d)
	return int(d[-1]) + m * toBase(d[:-1], m)
q = int(input())
found = {}
for _ in range(q):
	(d, m) = input().split()
	d = int(d)
	if isCorrBase(m, d):
		magic_numb = toBase(m, d)
		if magic_numb not in found:
			found[magic_numb] = 0
		found[magic_numb] += 1
comb = 0
for k in found.keys():
	comb += found[k] * (found[k] - 1) // 2
print(comb)


def f(a, b):
	rst = 0
	D = 10
	A = 1
	while b > 0:
		rm = b % D
		b = int(b / D)
		if rm >= a:
			return -1
		rst = rst + A * rm
		A = A * a
	return rst
T = int(input())
diccc = {}
for i in range(T):
	inn = input().split(' ')
	a = int(inn[0])
	b = int(inn[1])
	nb = f(a, b)
	if nb >= 0:
		if nb not in diccc.keys():
			diccc[nb] = 1
		else:
			diccc[nb] = diccc[nb] + 1
S = 0
for i in diccc:
	S = S + int(diccc[i] * (diccc[i] - 1) / 2)
print(S)


n = int(input().strip())
numeri = [0 for x in range(50)]
for i in range(n):
	(m, d) = [x for x in input().strip().split(' ')]
	m = int(m)
	if m == 1:
		continue
	if m == 10:
		numeri[int(d)] += 1
		continue
	continua = False
	numero = 0
	d = d[::-1]
	for i in range(len(d)):
		cifra = int(d[i])
		if cifra > m - 1:
			continua = True
			break
		numero += cifra if i == 0 else m * cifra
	if continua:
		continue
	numeri[numero] += 1
totale = 0
for numero in numeri:
	if numero != 0:
		totale += numero * (numero - 1) // 2
print(totale)


dic = {}
n = int(input())
for i in range(n):
	L = list(input().split())
	try:
		s = int(L[1], int(L[0]))
		if not s in dic:
			dic.update({s: 1})
		else:
			dic[s] = dic.get(s, None) + 1
	except:
		continue
z = 0
for (i, k) in dic.items():
	z += int(k * (k - 1) / 2)
print(z)


(a, b) = ([], {})
for _ in range(int(input())):
	(m, d) = input().split()
	try:
		a.append(int(str(d), int(m)))
	except:
		1
for i in a:
	if i in b:
		b[i] += 1
	else:
		b[i] = 1
ans = 0
for i in b:
	ans += b[i] * (b[i] - 1) // 2
print(ans)


import math

def fac1(n):
	if n < 2:
		return 0
	result = n - 1
	for i in range(2, n - 1):
		result *= i
	return result
T = int(input())
dates = []
valid_dates = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for _ in range(T):
	(a, b) = [x for x in input().split()]
	bi = int(b)
	ai = int(a)
	try:
		n = int(b, ai)
	except:
		continue
	dates += [n]
	valid_dates[n] += 1
sum = 0
for i in valid_dates:
	if i > 1:
		sum += i * (i - 1) // 2
print(sum)


from collections import Counter

def conv_func(m, d):
	valid_date = [[], []]
	valid_date.append([1, 10, 11])
	valid_date.append([1, 2, 10, 11, 12, 20, 21, 22])
	valid_date.append([1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30])
	valid_date.append([1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31])
	valid_date.append([1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, 30])
	valid_date.append([1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14, 15, 16, 20, 21, 22, 23, 24, 25, 26, 30, 31])
	valid_date.append([1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 30, 31])
	valid_date.append([1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30])
	valid_date.append([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31])
	valid_date.append([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30])
	valid_date.append([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31])
	if d not in valid_date[m]:
		return 0
	(d1, d2) = (d // 10, d - d // 10 * 10)
	return d1 * m + d2
calen = [[0 for i in range(32)] for i in range(13)]
for i_m in range(1, 13):
	for i_d in range(1, 32):
		calen[i_m][i_d] = conv_func(i_m, i_d)
N = int(input())
conv_to_10 = []
for i in range(N):
	(m, d) = [int(a) for a in input().split()]
	conv_to_10.append(calen[m][d])
conv_to_10 = [x for x in conv_to_10 if x > 0]
conv_set = set(conv_to_10)
iters = []
for c in conv_set:
	iters.append(conv_to_10.count(c))
iters = [x for x in iters if x > 1]
jokes = 0
for i in iters:
	jokes += i * (i - 1) // 2
print(jokes)


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

def convert(value, base):
	try:
		return int(str(value), base=base)
	except ValueError:
		return 0
values = [convert(e[1], e[0]) for e in entries]
repetitions = [0] * 365
for v in values:
	repetitions[v] += 1
print(sum(map(lambda x: x * (x - 1) // 2, repetitions[1:])))


n = int(input())
arr = []

def ans1(arr):
	if len(arr) == 0:
		return '0'
	ret = ''
	seen = {}
	count = 0
	for i in range(len(arr)):
		if str(arr[i]) in seen.keys():
			seen[str(arr[i])] += 1
		else:
			seen[str(arr[i])] = 1
	for x in seen.values():
		count += x * (x - 1) // 2
	return str(count)
for i in range(n):
	temp = [int(x) for x in input().split(' ')]
	num = 0
	m = str(temp[1])
	if not temp[0] == 10:
		success = True
		for i1 in range(len(m)):
			if int(m[len(m) - i1 - 1]) < temp[0]:
				num += int(m[len(m) - i1 - 1]) * temp[0] ** i1
			else:
				success = False
				break
		if success:
			arr.append(num)
	else:
		arr.append(temp[1])
print(ans1(arr))


import math

def number_to_list(n):
	num_list = []
	rev_num_list = []
	if n == 0:
		return [0]
	while n != 0:
		rev_num_list.append(n % 10)
		n = (n - n % 10) // 10
	for i in range(0, len(rev_num_list)):
		num_list.append(rev_num_list[len(rev_num_list) - i - 1])
	return num_list
n = int(input())
p = {}
for t in range(0, 40):
	p[t] = 0
for i in range(0, n):
	q = input().split()
	m = int(q[0])
	d = int(q[1])
	l = number_to_list(d)
	cond = True
	for i in range(0, len(l)):
		if l[i] >= m:
			cond = False
	r = 0
	if cond:
		for j in range(0, len(l)):
			r += l[j] * m ** (len(l) - j - 1)
		p[r] += 1
jokes = 0
for ev in p:
	if p[ev] >= 2:
		jokes += math.factorial(p[ev]) // (math.factorial(p[ev] - 2) * 2)
print(jokes)


d = {}

def valid(n, m):
	for i in n:
		if 0 <= int(i) < m:
			continue
		else:
			return False
	return True
for _ in range(int(input())):
	(m, n) = input().split()
	m = int(m)
	if m == 1:
		continue
	if valid(n, m):
		k = int(n, m)
		d[k] = d.get(k, 0) + 1
print(sum((d[i] * (d[i] - 1) // 2 for i in d)))


xs = [0 for _ in range(40)]
res = 0

def check(m, d):
	(base, ret) = (1, 0)
	while d:
		if d % 10 >= m:
			return -1
		else:
			ret += d % 10 * base
			base *= m
			d = d // 10
	return ret
for _ in range(int(input())):
	(m, d) = map(int, input().split())
	val = check(m, d)
	if val == -1:
		continue
	res += xs[val]
	xs[val] += 1
print(res)


def convert(m, d):
	mon = m
	day = d
	digits = []
	while day:
		temp = day % 10
		if temp >= mon:
			return 0
		digits.append(temp)
		day = day // 10
	res = digits[0]
	for x in digits[1:]:
		res += x * mon
		mon *= m
	return res
data = {}
for _ in range(int(input())):
	(m, d) = input().split(' ')
	(m, d) = (int(m), int(d))
	val = convert(m, d)
	if val == 0:
		pass
	elif val not in data:
		data.update({val: [(m, d)]})
	else:
		data[val].append((m, d))
jokes = 0
for (key, lst) in data.items():
	temp = len(lst)
	jokes += temp * (temp - 1) // 2
print('{0}'.format(jokes))


def fac(n):
	if n == 1 or n == 0:
		return 1
	else:
		return n * fac(n - 1)

def binom(n, k):
	return int(n * (n - 1) * 0.5)

def toDec(n, base):
	total = 0
	curr = n
	power = 0
	while curr:
		dig = curr % 10
		total += base ** power * dig
		curr //= 10
		power += 1
	return total

def toBase(n, base):
	out = 0
	power = 1
	curr = n
	digits = []
	digits.append(curr % base)
	while curr > base ** power:
		digits.insert(0, curr // base ** power)
		power += 1
	return int(''.join([str(k) for k in digits]))

def convert(n1, b1, b2):
	dec = toDec(n1, b1)
	n2 = toBase(dec, b2)
	return n2

def valid(n, base):
	curr = n
	while curr:
		if curr % 10 >= base:
			return False
		curr //= 10
	return True
N = int(input())
dates = []
counts = {}
for i in range(N):
	curr = [int(k) for k in input().split()]
	if valid(curr[1], curr[0]) and curr[0] != 1:
		curr = str(toDec(curr[1], curr[0]))
		if not curr in counts.keys():
			counts[curr] = 1
		else:
			counts[curr] += 1
total = 0
for i in counts.keys():
	total += binom(counts[i], 2)
print(total)


l = [0 for i in range(38)]
n = int(input())
for i in range(n):
	(m, d) = map(int, input().split())
	num = list(map(int, list(str(d))))
	q = 0
	if max(num) < m:
		for i in num:
			q = q * m + i
		l[q] += 1
q = 0
for i in l:
	q += i * (i - 1) // 2
print(q)


def conv(m, d):
	dNew = '0' + str(d)
	try:
		n = int(dNew, m)
		return n
	except Exception:
		return -1
N = int(input())
J = list()
for i in range(N):
	(m, d) = input().split()
	(m, d) = [int(m), int(d)]
	j = conv(m, d)
	if j > -1:
		J.append(j)
J.sort()
joke = 0
c = 1
for i in range(1, len(J)):
	if J[i] == J[i - 1]:
		c += 1
	else:
		joke += c * (c - 1) // 2
		c = 1
joke += c * (c - 1) // 2
print(joke)


def exp(x, n):
	r = 1
	while n:
		if n % 2:
			r *= x
		x *= x
		n //= 2
	return r
n = int(input())
l = []
for i in range(n):
	(m, d) = input().split()
	d1 = int(d)
	d = d[::-1]
	m = int(m)
	f = 0
	for c in d:
		if int(c) >= m:
			f = 1
			break
	if f == 0:
		if m == 10:
			l.append(d1)
		else:
			s = 0
			i = 0
			for c in d:
				s += int(c) * exp(m, i)
				i += 1
			l.append(s)
l.sort()
t = 0
q = 0
for i in range(1, len(l)):
	if l[i] != l[i - 1]:
		t += q * (q + 1) // 2
		q = 0
	else:
		q += 1
t += q * (q + 1) // 2
print(t)


from math import factorial
numdates = int(input())
listofdates = []
for n in range(numdates):
	listofdates += [input()]
base10dates = []
for n in listofdates:
	(m, d) = str.split(n)
	m = int(m)
	try:
		base10date = int(d, m)
		base10dates += [base10date]
	except ValueError:
		pass
counter_dict = {}
for n in base10dates:
	if n in counter_dict:
		counter_dict[n] += 1
	else:
		counter_dict[n] = 1
counter = 0
for n in counter_dict.values():
	if n != 1:
		counter += factorial(n) / (factorial(n - 2) * 2)
print(int(counter))


from collections import Counter
t = int(input().strip())
a = []
for a0 in range(t):
	flag = 0
	y = input().strip()
	x = y.split()
	m = int(x[0])
	d = x[1][::-1]
	n = [m, d]
	if m < 10:
		for i in d:
			z = int(i)
			if z >= m:
				flag = 1
				continue
	if flag == 0:
		a.append(n)
b = []
for j in a:
	sumi = 0
	count = 0
	for k in j[1]:
		sumi += j[0] ** count * int(k)
		count += 1
	b.append(sumi)
c = Counter(b)
d = c.values()
ways = 0
for l in d:
	ways += l * (l - 1) / 2
print(int(ways))


def get_num(n, b):
	res = 0
	mul = 1
	while n > 0:
		res += n % 10 * mul
		n //= 10
		mul *= b
	return res

def is_valid(n, b):
	if b > 1:
		while n > 0:
			dig = n % 10
			if dig >= b:
				return False
			n /= 10
		return True
	else:
		return False
counts = [0] * 38
T = int(input())
for _ in range(T):
	(b, n) = map(int, input().split(' '))
	if is_valid(n, b):
		dec = get_num(n, b)
		counts[dec] += 1
r = sum(map(lambda m: m * (m - 1) // 2, counts))
print(r)


def indexOfVal(d, item):
	return list(d.keys())[list(d.values()).index(item)]
noJokes = 0
dates = {}
for _ in range(int(input())):
	date = [int(i) for i in input().split()]
	try:
		val = int(str(date[1]), date[0])
		if val in dates.keys():
			noJokes += dates[val]
			dates[val] += 1
		else:
			dates[val] = 1
	except ValueError:
		pass
print(noJokes)


N = int(input())
count = 0
seen = {}
for i in range(N):
	(m, d) = input().split()
	b = int(m)
	if b < 2:
		continue
	x = 0
	for c in map(int, d):
		if c >= b:
			break
		x = x * b + c
	else:
		n = seen.get(x, 0)
		seen[x] = n + 1
		count += n
print(count)


import sys

def F(day, month):
	T = True
	sum = 0
	i = 0
	while day > 0:
		sum += day % 10 * month ** i
		if day % 10 >= month:
			T = False
		day //= 10
		i += 1
	if T:
		return sum
	else:
		return 0
N = int(input().strip())
A = [0 for i in range(10000)]
for i in range(N):
	(m, d) = input().strip().split(' ')
	(m, d) = [int(m), int(d)]
	A[F(d, m)] += 1
ans = 0
for i in range(1, 10000):
	ans += (A[i] ** 2 - A[i]) // 2
print(ans)


def convert_base(num, base):
	if base <= 1:
		return 0
	value = 0
	place = 1
	while num > 0:
		digit = num % 10
		if digit >= base:
			return 0
		value += digit * place
		num = (num - digit) // 10
		place *= base
	return value

def joke_pairs(D, n):
	H = {}
	for (m, d) in D:
		f = convert_base(d, m)
		if f and f in H:
			H[f] += 1
		else:
			H[f] = 1
	n_jokes = 0
	for val in H.values():
		n_jokes += val * (val - 1) // 2
	return n_jokes
n = int(input().strip())
D = []
for i in range(n):
	(m, d) = list(map(int, input().strip().split()))
	D.append((m, d))
print(joke_pairs(D, n))


from collections import defaultdict
d = defaultdict(int)
for _ in range(int(input())):
	(base, a) = input().split()
	base = int(base)
	try:
		v = int(a, base)
		d[v] += 1
	except ValueError:
		pass
ans = 0
for v in d.values():
	ans += v * (v - 1) // 2
print(ans)


import sys

def conv(x, b):
	s = '%d' % x
	n = len(s)
	val = 0
	for i in range(n):
		d = int(s[i])
		if d >= b:
			return None
		val *= b
		val += d
	return val
stat = {}
N = int(input())
for idx in range(N):
	(m, d) = map(int, input().split())
	val = conv(d, m)
	if val is None:
		continue
	if not val in stat:
		stat[val] = 0
	stat[val] += 1
s = 0
for val in stat:
	n = stat[val]
	s += n * (n - 1) // 2
print(s)


value = [[] for i in range(40)]

def compute_value(m, d):
	if d < 10:
		if d >= m:
			return 0
		else:
			return d
	else:
		first_digit = d // 10
		second_digit = d % 10
		if max(first_digit, second_digit) >= m:
			return 0
		else:
			return first_digit * m + second_digit
for i in range(int(input())):
	(m, d) = input().split(' ')
	value[compute_value(int(m), int(d))].append([int(m), int(d)])
result = 0
for i in range(1, 40):
	result += len(value[i]) * (len(value[i]) - 1) // 2
print(result)


t = int(input().strip())
B = dict()
count = 0
for _ in range(t):
	(m, d) = map(int, input().strip().split())
	try:
		n = int(str(d), m)
	except ValueError:
		continue
	B[n] = B.get(n, 0) + 1
for b in B.values():
	count += b * (b - 1) // 2
print(count)


N = int(input())
count = [0] * 1000
for i in range(N):
	dat = input().split()
	try:
		v = int(dat[1], int(dat[0]))
		count[v] += 1
	except ValueError:
		pass
total = 0
for i in count:
	total += i * (i - 1) // 2
print(total)


def main():
	N = int(input().strip())
	evts = dict()
	while N > 0:
		(m, d) = list(map(int, input().split()))
		try:
			e = int(str(d), m)
			evts[e] = evts.get(e, 0) + 1
		except ValueError:
			pass
		N -= 1
	cnt = 0
	for v in evts.values():
		cnt += v * (v - 1) // 2
	print(cnt)
main()


n = int(input())
l = []
c = []
for i in range(0, n):
	a = list(map(int, input().split()))
	if a in l:
		c[l.index(a)] = c[l.index(a)] + 1
	else:
		a1 = [int(d) for d in str(a[1])]
		if max(a1) < a[0]:
			l.append(a)
			c.append(1)
count = 0
for i in range(0, len(l)):
	if c[i] > 1:
		count = count + c[i] * (c[i] - 1) / 2
	for j in range(i + 1, len(l)):
		if int(str(l[i][1]), l[i][0]) == int(str(l[j][1]), l[j][0]):
			count = count + c[i] * c[j]
print(int(count))


from collections import Counter
n = int(input())

def jimandjokes(events):
	nums = [e for e in map(is_valid_event, events) if e != None]
	counts = Counter(nums)
	return sum([v * (v - 1) // 2 for v in counts.values()])

def is_valid_event(event):
	(month, day) = event
	day = list(map(int, str(day)))
	if month == 1 or any([d >= month for d in day]):
		return None
	else:
		return sum([day[-(1 + i)] * month ** i for i in range(len(day))])
events = [0] * n
for idx in range(n):
	(m, d) = map(int, input().split())
	events[idx] = (m, d)
print(jimandjokes(events))


def acc(n):
	assert n > 0
	return (n - 1) * n // 2
N = int(input())
md = list((tuple(map(int, input().split())) for _ in range(N)))
counts = dict()
for (m, d) in md:
	try:
		v = int(str(d), m)
		counts[v] = counts.get(v, 0) + 1
	except ValueError as e:
		pass
print(sum(map(acc, counts.values())))


from collections import defaultdict
n = int(input())
dic = defaultdict(int)
for i in range(n):
	total = 0
	(m, d) = input().split(' ')
	m = int(m)
	d = list(d)[::-1]
	fake = False
	power = 1
	for j in d:
		a = ord(j) - ord('0')
		if a >= m:
			fake = True
			break
		else:
			total += a * power
			power *= m
	if not fake:
		dic[total] += 1
ans = 0
for k in dic:
	ans += dic[k] * (dic[k] - 1) // 2
print(ans)


import sys
import collections as cl
T = int(input())
array = []
for _ in range(T):
	(m, d) = [int(temp) for temp in input().split()]
	if d // 10 >= m or d % 10 >= m:
		pass
	else:
		array.append(d // 10 * m + d % 10)
ans = 0
for c in cl.Counter(array).items():
	ans += c[1] * (c[1] - 1) // 2
print(ans)


from collections import Counter

def func(m, d):
	try:
		res = int(str(d), m)
	except ValueError:
		return None
	return res
dates = list((tuple(map(int, input().split())) for _ in range(int(input()))))
c = Counter((func(m, d) for (m, d) in dates))
del c[None]
print(sum((v * (v - 1) // 2 for v in c.values())))


import collections as cl
T = int(input())
array = []
for _ in range(T):
	(m, d) = [int(temp) for temp in input().split()]
	if d // 10 >= m or d % 10 >= m:
		pass
	else:
		array.append(d // 10 * m + d % 10)
ans = 0
for c in cl.Counter(array).items():
	ans += c[1] * (c[1] - 1) // 2
print(ans)


import collections as cl
T = int(input())
array = []
for _ in range(T):
	(m, d) = [int(temp) for temp in input().split()]
	if d // 10 >= m or d % 10 >= m:
		pass
	else:
		array.append(d // 10 * m + d % 10)
ans = 0
c = cl.Counter(array)
for c in cl.Counter(array).items():
	ans += c[1] * (c[1] - 1) // 2
print(ans)


d = {}
n = int(input())
for _ in range(n):
	(m, e) = map(int, input().split())
	nn = 0
	f = True
	for k in str(e):
		if int(k) >= m:
			f = False
		nn = nn * m + int(k)
	if f:
		if nn in d:
			d[nn] += 1
		else:
			d[nn] = 1
r = 0
for i in d.values():
	r += i * (i - 1) // 2
print(r)


from collections import defaultdict
Events = defaultdict(int)
N = int(input())
for _ in range(N):
	(m, d) = input().split()
	try:
		Events[int(d, int(m))] += 1
	except:
		pass
print(sum((x * (x - 1) // 2 for x in Events.values())))


import sys

def solve(jj):

	def rdigit_gen(n):
		if n == 0:
			yield 0
		else:
			while n != 0:
				yield (n % 10)
				n //= 10

	def calc(base, k):
		(sm, c) = (0, 1)
		for d in rdigit_gen(k):
			if d >= base:
				return None
			sm += c * d
			c *= base
		return sm
	cache = dict()
	for (base, k) in jj:
		u = calc(base, k)
		if u is not None:
			if u not in cache:
				cache[u] = 1
			else:
				cache[u] += 1
	rval = 0
	for c in cache.values():
		rval += c * (c - 1) // 2
	return rval
jj = []
n = int(input())
for _ in range(n):
	(base, k) = map(int, input().split())
	jj.append((base, k))
print(solve(jj))


import collections as cl
T = int(input())
array = []
for _ in range(T):
	(m, d) = [int(temp) for temp in input().split()]
	if d // 10 >= m or d % 10 >= m:
		pass
	else:
		array.append(d // 10 * m + d % 10)
ans = 0
for c in cl.Counter(array).items():
	ans += c[1] * (c[1] - 1) // 2
print(ans)


import collections as cl
T = int(input())
array = []
for _ in range(T):
	(m, d) = [int(temp) for temp in input().split()]
	if d // 10 >= m or d % 10 >= m:
		pass
	else:
		array.append(d // 10 * m + d % 10)
ans = 0
for c in cl.Counter(array).items():
	ans += c[1] * (c[1] - 1) // 2
print(ans)