Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, S = [int(input()), int(input())]


def solve1():
    i = 2
    while i * i <= N:
        s, n = 0, N
        while n > 0:
            s += n % i
            n //= i
        if s == S:
            return i

        i += 1

    return 1 << 60


def solve2():
    i = 1
    ret = 1 << 60
    while i * i <= N:
        b = (N - S) // i + 1
        s, n = 0, N
        while n > 0:
            s += n % b
            n //= b
        if s == S:
            ret = min(ret, b)
        i += 1

    return ret


def solve():
    ret = min(solve1(), solve2())
    return ret if ret != 1 << 60 else -1


print(solve())


Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, S = [int(input()), int(input())]


def solve1():
    i = 2
    while i * i <= N:
        if ok(i, N, S):
            return i

        i += 1

    return 1 << 60


def solve2():
    i = 1
    ret = 1 << 60
    while i * i <= N:
        b = (N - S) // i + 1
        if ok(b, N, S):
            ret = min(ret, b)
        i += 1

    return ret


def ok(b, N, S):
    if b <= 1:
        return False

    s, n = 0, N
    while n > 0:
        s += n % b
        n //= b

    return s == S



def solve():
    if S == N:
        return N + 1
    ret = min(solve1(), solve2())
    return ret if ret != 1 << 60 else -1


print(solve())
Buggy python submission (verdict: Runtime Error):
from sys import stdin
input = stdin.readline
count = 0
def solve():
    n,m = map(int,input().split())
    p = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    father = [-1] * n    # store the opposite of members in the union
    count = n
    def getfather(x):
        if father[x] < 0: return x
        father[x] = getfather(father[x])
        return father[x]


    def union(x, y):
        x = getfather(x)
        y = getfather(y)
        nonlocal count
        if x != y:
            count -= 1
            if father[x] > father[y]:
                x,y = y,x
            father[x] += father[y]
            father[y] = x
    for a,b in p:
        union(a,b)
    print(count - 1)

if __name__ == '__main__':
    solve()

Fixed submission:
from sys import stdin
input = stdin.readline

def solve():
    n,m = map(int,input().split())
    p = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    father = [-1] * n
    count = n
    def getfather(x):
        if father[x] < 0: return x
        father[x] = getfather(father[x])
        return father[x]


    def union(x, y):
        x = getfather(x)
        y = getfather(y)
        nonlocal count
        if x != y:
            count -= 1
            if father[x] > father[y]:
                x,y = y,x
            father[x] += father[y]
            father[y] = x

    for a,b in p:
        union(a-1,b-1)
        
    print(count - 1)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
MOD = 998244353


def solve():
    N,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    # @lru_cache(None)
    # def dp(n):
    #     if n == 1:
    #         return 1
    #     res = 0
    #     for a,b in step:
    #         if n <= a:
    #             continue
    #         for i in range(a,b+1):
    #             if n > i:
    #                 res += dp(n-i)
    #     return res % MOD
    #
    # print(dp(N))

    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for a,b in step:
            if i <= a:
                continue
            for j in range(a,b+1):
                if i > j:
                    dp[i] += dp[i-j]
        dp[i] %= MOD
    print(dp[N])



if __name__ == '__main__':
    solve()


Fixed submission:
from sys import stdin
input = stdin.readline
mod = 998244353
from collections import defaultdict

def solve():
    n,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    dp=defaultdict(int)

    f=0
    dp[1]=1
    for i in range(1,1+n):
        for r,l in step:
            f=(f+-dp[i-1-l]+dp[i-r])%mod
        dp[i]=(dp[i]+f)%mod
    print(dp[n])



if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
from sys import stdin

input = stdin.readline
from functools import lru_cache

MOD = 998244353


def solve():
    N,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]\


    @lru_cache(None)
    def dp(n):
        if n == 1:
            return 1
        res = 0
        for a,b in step:
            if n <= a:
                continue
            for i in range(a,b+1):
                if n > i:
                    res += dp(n-i)
        return res % MOD

    print(dp(N))


if __name__ == '__main__':
    solve()


Fixed submission:
from sys import stdin
input = stdin.readline
mod = 998244353
from collections import defaultdict

def solve():
    n,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    dp=defaultdict(int)

    f=0
    dp[1]=1
    for i in range(1,1+n):
        for r,l in step:
            f=(f+-dp[i-1-l]+dp[i-r])%mod
        dp[i]=(dp[i]+f)%mod
    print(dp[n])



if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
from sys import stdin
from itertools import accumulate

input = stdin.readline
from collections import Counter

N, M = map(int, input().split())
friends = [tuple(map(int, inp.strip().split())) for inp in stdin.read().splitlines()]
father = list(range(N))


def getfather(x):
    if father[x] != x:
        father[x] = getfather(father[x])
    return father[x]


def union(x, y):
    fx = getfather(x)
    fy = getfather(y)
    if fx != fy:
        father[fx] = fy


for a, b in friends:
    union(a - 1, b - 1)
print(max(Counter([getfather(i) for i in range(N)]).values()))


Fixed submission:
from sys import stdin


input = stdin.readline


N, M = map(int, input().split())
friends = [tuple(map(int, inp.strip().split())) for inp in stdin.read().splitlines()]
father = [-1] * N


def getfather(x):
    if father[x] < 0: return x
    father[x] = getfather(father[x])
    return father[x]


def union(x, y):
    x = getfather(x)
    y = getfather(y)
    if x != y:
        if father[x] > father[y]:
            x,y = y,x
        father[x] += father[y]
        father[y] = x;


for a, b in friends:
    union(a - 1, b - 1)
# print(max(Counter([getfather(i) for i in range(N)]).values()))
print(max([-father[getfather(i)] for i in range(N)] or [0]) )

Buggy python submission (verdict: Runtime Error):
from sys import stdin
from itertools import accumulate
input = stdin.readline
from collections import Counter
N,M = map(int,input().split())
friends = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
father = list(range(N))
def getfather(x):
    if father[x] != x:
        father[x] = getfather(father[x])
    return father[x]
def union(x,y):
    fx = getfather(x)
    fy = getfather(y)
    if fx != fy:
        father[fx] = fy
for a,b in friends:
    union(a-1,b-1)
print(max(Counter([getfather(i) for i in range(N)]).values()))

Fixed submission:
from sys import stdin


input = stdin.readline


N, M = map(int, input().split())
friends = [tuple(map(int, inp.strip().split())) for inp in stdin.read().splitlines()]
father = [-1] * N


def getfather(x):
    if father[x] < 0: return x
    father[x] = getfather(father[x])
    return father[x]


def union(x, y):
    x = getfather(x)
    y = getfather(y)
    if x != y:
        if father[x] > father[y]:
            x,y = y,x
        father[x] += father[y]
        father[y] = x;


for a, b in friends:
    union(a - 1, b - 1)
# print(max(Counter([getfather(i) for i in range(N)]).values()))
print(max([-father[getfather(i)] for i in range(N)] or [0]) )
Buggy python submission (verdict: Runtime Error):
from sys import stdin,exit
import collections

input = stdin.readline

Y, X, M = map(int, input().split())
bomb = set([tuple(map(int,inp.split())) for inp in stdin.read().splitlines()])
cx = collections.defaultdict(int)
cy = collections.defaultdict(int)
for y,x in bomb:
    cx[x] += 1
    cy[y] += 1
mx = max(cx.values())
my = max(cy.values())
candidateX = [x for (x,v) in cx.items() if v == mx]
candidateY = [y for (y,v) in cy.items() if v == my]
res = mx + my -1
for x in candidateX:
    for y in candidateY:
        if (y,x) not in bomb:
            print(res + 1)
            exit(1)

print(res)

Fixed submission:
from sys import stdin
import collections

input = stdin.readline

Y, X, M = map(int, input().split())
bomb = set([tuple(map(int,inp.split())) for inp in stdin.read().splitlines()])
cx = collections.defaultdict(int)
cy = collections.defaultdict(int)
for y,x in bomb:
    cx[x] += 1
    cy[y] += 1
mx = max(cx.values())
my = max(cy.values())
candidateX = [x for (x,v) in cx.items() if v == mx]
candidateY = [y for (y,v) in cy.items() if v == my]
res = mx + my -1
for x in candidateX:
    for y in candidateY:
        if (y,x) not in bomb:
            res += 1
            break
    else:
        continue
    break
print(res)
Buggy python submission (verdict: Runtime Error):
from sys import stdin

input = stdin.readline



def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    left = 0
    right = max(a)

    def ok(l):
        s = sum([i // l for i in a])
        return s <= k

    while left < right:
        mid = (left + right) // 2
        if ok(mid):
            right = mid
        else:
            left = mid + 1
    print(left)


if __name__ == '__main__':
    solve()


Fixed submission:
from sys import stdin

input = stdin.readline
import math
import heapq


def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    left = 1
    right = max(a)

    def ok(l):
        s = sum([(i-1) // l for i in a])
        return s <= k
    while left < right:
        mid = (left + right) // 2
        if ok(mid):
            right = mid
        else:
            left = mid + 1
    print(left)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
from sys import stdin

input = stdin.readline
from collections import defaultdict


class BIT:
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N + 1)

    def add(self, ind, x=1):
        ind += 1
        while ind <= self.N:
            self.arr[ind] += x
            ind += (ind & -ind)

    def get_sum(self, ind):
        ind += 1
        res = 0
        while ind > 0:
            res += self.arr[ind]
            ind -= (ind & -ind)
        return res


def solve():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
    prev = [-1] * N
    nxt = [-1] * N
    for i, v in enumerate(c):
        if prev[v] != -1:
            nxt[prev[v]] = i
        prev[v] = i
    q = defaultdict(list)
    for i, (l, r) in enumerate(query):
        q[l - 1].append((r - 1, i))
    bit = BIT(N)
    ans = [0] * Q
    for l in range(N - 1, -1, -1):
        if nxt[l] != -1:
            bit.add(nxt[l], 1)
        for r, i in q[l]:
            ans[i] = r - l + 1 - bit.get_sum(r)
    for a in ans:
        print(a)

if __name__ == '__main__':
    solve()


Fixed submission:
from sys import stdin

input = stdin.readline
from collections import defaultdict


class BIT:
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N + 1)

    def add(self, ind, x=1):
        ind += 1
        while ind <= self.N:
            self.arr[ind] += x
            ind += (ind & -ind)

    def get_sum(self, ind):
        ind += 1
        res = 0
        while ind > 0:
            res += self.arr[ind]
            ind -= (ind & -ind)
        return res


def solve():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    query = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
    prev = [-1] * (N+1)
    nxt = [-1] * (N+1)
    for i, v in enumerate(c):
        if prev[v] != -1:
            nxt[prev[v]] = i
        prev[v] = i
    q = defaultdict(list)
    for i, (l, r) in enumerate(query):
        q[l - 1].append((r - 1, i))
    bit = BIT(N)
    ans = [0] * Q
    for l in range(N - 1, -1, -1):
        if nxt[l] != -1:
            bit.add(nxt[l], 1)
        for r, i in q[l]:
            ans[i] = r - l + 1 - bit.get_sum(r)
    for a in ans:
        print(a)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
from sys import stdin

input = stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=abs, reverse=True)
    noneg = 1
    res = 1
    i = 0
    platest = -1
    nlatest = -1
    ind = set()
    while i < k:
        if a[i] > 0:
            ind.add(i)
            platest = i
        elif a[i] < 0:
            if noneg:
                noneg = 0
                nlatest = i
            else:
                noneg = 1
                ind |= {nlatest, i}
        i += 1
    if not noneg:
        pnext = -1
        nnext = -1
        while i < N and (pnext == -1 or nnext == -1):
            if a[i] > 0 and pnext == -1:
                pnext = i
            elif a[i] < 0 and nnext == -1:
                nnext = i
            i += 1
        t1 = float('-inf')
        t2 = float('-inf')
        if platest != -1 and nnext != -1:
            t1 = abs(a[nnext]) / a[platest]
        if pnext != -1:
            t2 = a[pnext] / abs(a[nlatest])
        else:
            if a[-1] == 0:
                print(0)
                return
            else:
                res = 1
                for i in range(N-1,N-k-1,-1):
                    res *= a[i]
                    res %= MOD
                print(res)
                return
        if t1 >= t2:
            ind.discard(platest)
            ind.add(a[nnext])
        else:
            ind.discard(nlatest)
            ind.add(a[pnext])
        res = 1
    for i in ind:
        res *= a[i]
        res %= MOD
    print(res)



if __name__ == '__main__':
    solve()


Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
            ans %= MOD
        print(ans)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
            ans %= MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from sys import stdin, setrecursionlimit
# input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

dp = [-1] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))


Fixed submission:
"""
https://atcoder.jp/contests/dp/tasks/dp_a
"""
from sys import stdin

n = int(input())
h = list(map(int, stdin.readline().strip().split()))

dp = [float('inf') for _ in range(n)]

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

print(dp[n - 1])

Buggy python submission (verdict: Runtime Error):
# using dp with memoization, TLE
from sys import stdin
N, W = map(int, input().split())
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]

dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print(dp[W])


Fixed submission:
"""
https://atcoder.jp/contests/dp/tasks/dp_a
"""
from sys import stdin

n = int(input())
h = list(map(int, stdin.readline().strip().split()))

dp = [float('inf') for _ in range(n)]

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

print(dp[n - 1])
Buggy python submission (verdict: Runtime Error):
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

dp = [-1] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))


Fixed submission:
from sys import stdin, setrecursionlimit
# input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

dp = [-1] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))

Buggy python submission (verdict: Runtime Error):
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

dp = [-1] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N)))


Fixed submission:
from sys import stdin, setrecursionlimit
# input = stdin.readline
setrecursionlimit(200000)
N, M = map(int, input().split())
# d = [0] * (N + 1)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    adj[x].append(y)
    # d[y] += 1

dp = [-1] * (N + 1)


def lp(x: 'int') -> 'int':
    if dp[x] >= 0:
        return dp[x]
    else:
        dp[x] = 0
        for y in adj[x]:
            dp[x] = max(dp[x], lp(y) + 1)
        return dp[x]


print(max(lp(i) for i in range(1, N + 1)))
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)

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

INF = -(10**13)

dp = [[INF] * (N + 1) for _ in range(N + 1)]


def play(start: 'int',
         end: 'int') -> 'int':  # return the maximum X for range[start,end)
    # if start + 1 == end:
    #     return start
    if dp[start][end] != INF:
        return dp[start][end]
    length = end - start
    if (N - length) & 1 == 0:  # taro plays
        if length == 1:
            dp[start][end] = a[start]
            return a[start]
        else:
            dp[start][end] = max(a[start] + play(start + 1, end),
                                 a[end - 1] + play(start, end - 1))
            return dp[start][end]
    else:  # jiro plays
        if length == 1:
            dp[start][end] = 0
            return 0
        else:
            dp[start][end] = min(play(start + 1, end), play(start, end - 1))
            return dp[start][end]


print(2 * play(0, N) - sum(a))


Fixed submission:
from sys import stdin
input = stdin.readline

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

dp = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    dp[i][i + 1] = a[i] if N & 1 == 1 else -a[i]

for j in range(2, N + 1):
    for i in range(0, N + 1 - j):
        # j is the length of the interval + 1
        if (N - j) & 1 == 0:
            dp[i][i + j] = max(a[i] + dp[i + 1][i + j],
                               a[i + j - 1] + dp[i][i + j - 1])
        else:
            dp[i][i + j] = min(dp[i + 1][i + j] - a[i],
                               dp[i][i + j - 1] - a[i + j - 1])

print(dp[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
final_ans = 1
for h in range(2,N):
         n = h
         x = n
         ans = []
         for i in range(2,int(x**(1/2))+1):
                  if n % i == 0:
                           soinsuu = i
                           zyousuu = 0
                           while n % i == 0:
                                    n = n // i
                                    zyousuu += 1
                           ans.append([soinsuu,zyousuu])
         if n != 1:
                  ans.append([n,1])
         tmp = 1
         for j in range(len(ans)):
                  tmp *= (ans[j][1] + 1)
         final_ans += tmp
print(final_ans)
                  
                  


Fixed submission:
n = int(input())
ans = 0
for i in range(1,n):
         ans += ((n-1) // i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
q = int(input())
for i in range(q):
         b,c = map(int,input().split())
         a = [c if i == b else i for i in a]
         print(sum(a))



Fixed submission:
import collections
import copy
n = int(input())
a = list(map(int,input().split()))
suma = sum(a)
numcount = [0] * ((10 ** 5) + 1)
for i in range(n):
         numcount[a[i]] += 1
q = int(input())
for i in range(q):
         b,c = map(int,input().split())
         if numcount[b] != 0:
                  tmpb = numcount[b]
                  numcount[c] += numcount[b]
                  numcount[b] = 0
                  suma += tmpb*(c - b)
         print(suma)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
         ans *= a[i]
if ans > (10**18):
         print(-1)
else:
         print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 1
for i in range(n):
         ans *= a[i]
         if ans == 0:
                  print(ans)
                  exit()
         elif ans > (10 ** 18):
                  print(-1)
                  exit()
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = list((input()))
ans = 0
for i in range(len(s)):
         for j in range(i,len(s)):
                  tmp = s[i:j+1]
                  tmp = int("".join(tmp))
                  if tmp % 2019 == 0:
                           ans += 1
print(ans)


Fixed submission:
p = 2019
s = [int(i) for i in input()]
p_cnt = 0
 
s = s[::-1]
div_dic = dict(zip(range(p), [0] * p))
tmp = 0

for i in range(len(s)):
    tmp += s[i] * pow(10, i, p)
    tmp %= p
    div_dic[tmp] += 1

for v in div_dic.values():
    p_cnt += v * (v - 1)
p_cnt //= 2
p_cnt += div_dic.get(0)
 
print(p_cnt)