Harryxun/stf_run huggingface dataset:
from collections import defaultdict
import sys
from fractions import Fraction

count = defaultdict(int)
N = int(sys.stdin.readline())

edges = defaultdict(list)
for i in range(N):
    A, B = [int(x) for x in sys.stdin.readline().split()]
    if B == 0:
        angle = "I"
    else:
        angle = Fraction(A, B)
    count[angle] += 1

ZERO = Fraction(0, 1)
pairs = {}
solos = []
for k1 in count:
    if k1 in pairs:
        continue
    if k1 == "I":
        if ZERO in count:
            pairs[ZERO] = k1
        continue

    for k2 in count:
        if k2 == ZERO:
            continue
        if k1 * k2 == -1:
            pairs[k2] = k1
            break
    else:
        solos.append(k1)
# print(pairs, solos)

P = 1000000007


def pow2(n):
    if n < 30:
        return 2 ** n

    p = pow2(n // 2)
    pp = (p * p) % P
    if n % 2 == 1:
        return (2 * pp) % P
    else:
        return pp


result = 1
for p in pairs:
    # print("pair", p, count[p], pairs[p], count[pairs[p]])
    n = count[p]
    m = count[pairs[p]]
    result = result * ((pow2(n) - 1) + (pow2(m) - 1) + 1) % P
for k in solos:
    # print("solo", k, count[k])
    result = result * pow2(count[k]) % P

print(result - 1)


### FIXED CODE ###

from collections import defaultdict
import sys
from math import gcd
count = defaultdict(int)
N = int(sys.stdin.readline())

zeros = 0
for i in range(N):
    A, B = [int(x) for x in input().split()]
    if A == B == 0:
        zeros += 1
        continue
    if A == 0:
        angle = (0, 1)
    elif B == 0:
        angle = (1, 0)
    else:
        sgn = A // abs(A)
        g = gcd(A, B)
        angle = (A // sgn // g, B // sgn // g)

    count[angle] += 1
# print(count)

pairs = {}
solos = []
for k1 in count:
    if k1 in pairs:
        continue
    if k1 == (0, 1):
        if (1, 0) in count:
            pairs[(1, 0)] = k1
        else:
            solos.append(k1)
        continue

    A, B = k1
    if B:
        sgn = -B // abs(B)
        k2 = (-B // sgn, A // sgn)
    else:
        k2 = (0, 1)
    if k2 in count:
        pairs[k2] = k1
    else:
        solos.append(k1)
#print(pairs, solos)

P = 1000000007


def pow2(n):
    # if n < 30:
    #     return 2 ** n

    # p = pow2(n // 2)
    # pp = (p * p) % P
    # if n % 2 == 1:
    #     return (2 * pp) % P
    # else:
    #     return pp
    return pow(2, n, P)


result = 1
for p in pairs:
    # print("pair", p, count[p], pairs[p], count[pairs[p]])
    n = count[p]
    m = count[pairs[p]]
    result = result * ((pow2(n) - 1) + (pow2(m) - 1) + 1) % P
for k in solos:
    # print("solo", k, count[k])
    result = result * pow2(count[k]) % P

print((result + zeros - 1) % P)
import numpy as np

a, b, q = map(int, input().split())
sh = []
te = []


def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]


def checkshrine(x):
    x_near_sh = getNearestValue(sh, x)
    xsash = np.abs(x_near_sh - x)
    sh_near_te = getNearestValue(te, x_near_sh)
    return xsash + np.abs(sh_near_te - x_near_sh)


def checktemple(x):
    x_near_te = getNearestValue(te, x)
    xsate = np.abs(x_near_te - x)
    te_near_sh = getNearestValue(sh, x_near_te)
    return xsate + np.abs(te_near_sh - x_near_te)


for i in range(a):
    sh.append(int(input()))

for i in range(b):
    te.append(int(input()))

for i in range(q):
    x = int(input())
    checkshrinevalue = checkshrine(x)
    checktemplevalue = checktemple(x)
    if (checkshrinevalue > checktemplevalue):
        print(checktemplevalue)
    else:
        print(checkshrinevalue)


### FIXED CODE ###


import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
import sys
inputs = sys.stdin.readlines()
n = int(inputs[0])
L = list(map(int, inputs[1].split())
A = sorted(L)

ans = 0
for i in range(n-1, 0, -1):
    l, r = 0, i-1
    while l < r:
        if A[i] < A[l] + A[r]:
            ans += r-l
            r -= 1
        else:
            l += 1

print(ans)

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()
n = int(inputs[0])
L = list(map(int, inputs[1].split()))
A = sorted(L)
 
ans = 0
for i in range(n-1, 0, -1):
    l, r = 0, i-1
    while l < r:
        if A[i] < A[l] + A[r]:
            ans += r-l
            r -= 1
        else:
            l += 1

print(ans)
h,w = map(int,input().split())
for i in range(h):
  s=str(input())
  print(s)
  print(s)

### FIXED CODE ###

s = input()
b = ['a','e','i','o','u']
for i in b:
  if s == i:
    print('vowel')
    exit()
print('consonant')
a,b = map(int,inout().split())
print(a*b)

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b)
import numpy as np

def resolve():
    import sys
    input = sys.stdin.readline
    xn = [int(x) for x in input().rstrip().split()]
    x = xn[0]
    n = xn[1]
	
    if n == 0:
      print(x)
      exit()
    
    p = [int(x) for x in input().rstrip().split()]
    num_list = [i for i in range(1, 101) if not i in p]

    idx = np.abs(np.asarray(num_list) - x).argmin()
    print(num_list[idx])



# x = list(map(int, input().split()))

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

import numpy as np

def resolve():
    import sys
    input = sys.stdin.readline
    xn = [int(x) for x in input().rstrip().split()]
    x = xn[0]
    n = xn[1]
	
    if n == 0:
      print(x)
      exit()
    
    p = [int(x) for x in input().rstrip().split()]
    num_list = [i for i in range(0, 102) if not i in p]

    idx = np.abs(np.asarray(num_list) - x).argmin()
    print(num_list[idx])



# x = list(map(int, input().split()))

if __name__ == "__main__":
    resolve()
N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
x = [None] * (N+1)

def fail():
    print("No")
    # exit()

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            dfs(t)
        else:
            if x[t] != x[s] + d:
                fail()

for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1].append([R-1,  D])
    G[R-1].append([L-1, -D])

for i in range(N):
    if x[i] is None:
        x[i] = 0
        dfs(i)

print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
x = [None] * (N)

def dfs(s):
    global x, G
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            if not dfs(t):
                return False
        else:
            if x[t] != x[s] + d:
                return False
    return True

for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1].append([R-1,  D])
    G[R-1].append([L-1, -D])

ans = True
for i in range(N):
    if x[i] is None:
        x[i] = 0
        ans &= dfs(i)

print("Yes" if ans else "No")
n = int(input())
s = input()
if n % 2 = 0 and s[0 , n//2 - 1] =s[n//2 , n - 1]:
  print('Yes')
 else:
  print('No')


### FIXED CODE ###

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

if n%2:
  print('No')
else:
  if s[:n//2]==s[n//2:]:
    print('Yes')
  else:
    print('No')
from functools import lru_cache

@lru_cache(maxsize=100000)
def dp(rest,score):
    ansbox=[]
    scorebox=[]
    for i in m_list:
        if (rest-i)>0:
            ansbox.append(dp(rest-i,score+1))
            scorebox.append(dp(rest-i, score+1)[1])
    if ansbox:
        max_index=scorebox.index(max(scorebox))
        return ansbox[max_index][0],ansbox[max_index][1]
    else:

        return rest,score
    pass

N,X=map(int,input().split())
m_list=[]
newX=X
sum=0
for i in range(N):
    inp=int(input())
    m_list.append(inp)
    newX-=inp

score=dp(newX,N)

print(score[1])


### FIXED CODE ###

N,X=map(int,input().split())
M=[int(input()) for _ in range(N)]
print(len(M)+(X-sum(M))//min(M))
n,k = map(int, input().split())
a = sorted([tuple(input().split()) for i in range(n)])
ans = 0
for x in a:
  temp = min(x[1],k)
  ans += temp*x[0]
  k = max(0,k-temp)
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
a = sorted(tuple(map(int,input().split())) for i in range(n))
ans = 0
for x in a:
  temp = min(x[1],k)
  ans += temp*x[0]
  k = max(0,k-temp)
print(ans)
N=int(input())
list1=[]
for i in range(N):
  x1=list(map(int,input().split()))
  list1.append(x1)
flag=0
for i in range(101):
  for j in range(101):
    list2=[]
    for k in range(N):
      Hx=list1[k][2]+abs(list1[k][0]-i)+abs(list1[k][1]-j)
      list2.append(Hx)
    if len(set(list2))==1:
      list3=[0]
      for l in range(N):
         d=Hx-abs(list1[l][0]-i)-abs(list1[l][1]-j)
         list3.append(d)
      if min(list3)>=0:
         print(i,j,Hx)
         flag=1
      else:
        pass
    else:
      pass
    if flag==1:
      break
  if flag==1:
    break

### FIXED CODE ###

n=int(input())
if n==1:
  print('Hello World')
else:
  A=int(input())
  B=int(input())
  print(A+B)
a,b,c=map(int,input().split())
for i in range(1,b+1):
    if (a*i)%b==c:
        print("YES")
        break
else:
    print("NO")
        


### FIXED CODE ###

A,B,C=input().split()
if (A[::-1])[0]==B[0] and (B[::-1])[0]==C[0]:
    print("YES")
else:
    print("NO")
s=input()
s[3]="8"
print(s)

### FIXED CODE ###

s=list(input())
s[3]="8"
ans=""
for i in range(len(s)):
  ans+=s[i]
print(ans)
def noboru(i, a2, a1):
    if (i == 0 or i == 1):
        return a1
    elif (i == 2):
        return a2
    else:
        return noboru(i-1, a2+a1, a2)


def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans *= noboru(a[i] - pos - 1, 2, 1)
            pos = a[i] + 1
    ans *= noboru(N - pos, 2, 1)
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a) % 1000000007)

### FIXED CODE ###

CONST = 1000000007

def noboru(n):
    a1 = 1
    a2 = 2
    ans = 0
    if (n == 0 or n == 1): return a1
    elif (n == 2): return a2
    else:
        for i in range(1, n-1):
            ans = a2 + a1
            a1 = a2
            a2 = ans
        return a2

def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1)) % CONST
            pos = a[i] + 1
    ans = (ans * noboru(N - pos)) % CONST
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a))
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M, K = il()
    A = il()
    SA = [0] * (N + 1)
    for n in range(N):
        SA[n + 1] = A[n] + SA[n]
    B = il()
    SB = [0] * (M + 1)
    for m in range(M):
        SB[m + 1] = B[m] + SA[m]

    ret = 0
    for n in range(N+1):
        for m in range(M+1):
            if SA[n] + SB[m] <= K:
                ret = max(ret, n + m)
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M, K = il()
    A = list(itertools.accumulate([0] + il()))
    B = list(itertools.accumulate(([0] + il())))

    ret, m = 0, M
    for n in range(N+1):
        if A[n] > K:
            break

        while B[m] > K - A[n]:
            m -= 1
        ret = max(ret, n+m)
    print(ret)




if __name__ == '__main__':
    main()
from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 1)


### FIXED CODE ###

from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 1)
n = int(raw_input)
a = map(int, raw_input().split())

for i in range(n, 0):
    print a[i],

### FIXED CODE ###

n = int(raw_input())
a = map(int, raw_input().split())
a.reverse()
print (" ".join(map(str, a)))
import math
A,B,K=map(int,input().split())
d=[]
for i in range(1,max(A,B)+1):
    if A%i==0 and B%i==0:
        d.append(i)
print(d[len(d)-K])

### FIXED CODE ###

A,B,C=map(int,input().split())
if B>A*C:
    print(C)
else:
    print(B//A)
def get_ncr():
    cache = {}

    def f(*args):
        if args in cache:
            return cache[args]
        n, r = args
        if r == 0 or n == r:
            cache[args] = 1
            return 1
        cache[args] = f(n - 1, r) + f(n - 1, r - 1)
        return cache[args]

    return f


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


n = int(input())
aa = list(map(int, input().split()))
i1, i2 = find_duplicated(aa)
pre_n = i1
mid_n = i2 - i1 + 1
post_n = n + 1 - i2 - 1
ncr = get_ncr()
div = int(1e9 + 7)

for total in range(1, n + 2):
    ans = 0
    for i in range(max(total - pre_n - post_n, 0), min(total, mid_n) + 1):
        if i == 1:
            ic = mid_n - 1
        else:
            ic = ncr(mid_n, i)
        for j in range(max(total - i - post_n, 0), min(total - i, pre_n) + 1):
            k = total - i - j
            ans = (ans + ic * ncr(pre_n, j) * ncr(post_n, k)) % div
    print(ans)


### FIXED CODE ###

def ncr(n, r):
    return fact[n] * inv_fact[r] * inv_fact[n - r] % div


def find_duplicated(aa):
    appeared = [-1] * (n + 1)
    for i, a in enumerate(aa):
        if appeared[a] >= 0:
            return appeared[a], i
        appeared[a] = i


div = int(1e9 + 7)
n = int(input())
aa = list(map(int, input().split()))

fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, n + 2):
    fact_tmp *= i
    fact_tmp %= div
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, div - 2, div))

i1, i2 = find_duplicated(aa)
outside_n = n + 1 - (i2 - i1 + 1)

for part_n in range(1, n + 2):
    sub = ncr(outside_n, part_n - 1) if outside_n >= part_n - 1 else 0
    print((ncr(n + 1, part_n) - sub) % div)
# -*- coding: utf-8 -*-

import sys
import math

def saiki(n,saiki_one_count,do_count):
    do_count += 1
    mod = n % saiki_one_count
    if mod == 0:
        return do_count
    saiki_one_count = bin(mod).count("1")
    return saiki(mod,saiki_one_count,do_count)
def main():
    input = sys.stdin.readline
    N = int(input())
    x = input()
    x_list = list(x)[:-1]
    x_list = [int(value) for value in x_list]
    one_count = x_list.count(1)
    sum_x = 0
    for i in range(len(x_list)):
        if x_list[N -1 - i] == 1:
            sum_x += 2 ** i
    zero_convert = sum_x%(one_count+1)
    one_convert = sum_x%(one_count+1)

    for i in range(len(x_list)):
        current_sum_x = 0
        current_one_count = 0
        if x_list[i] == 0:
            current_one_count = one_count + 1
            current_sum_x = zero_convert + pow(2,N-i-1,current_one_count)
        else:
            current_one_count = one_count - 1
            current_sum_x = one_convert + pow(2,N-i-1,current_one_count)
        do_count = saiki(current_sum_x,current_one_count,0)
        print(do_count)
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202007_2nd/D_input.txt")
else:
    f=sys.stdin
#from 2nd count
def cnt_func(num):
    cnt=0
    while num:
        num%=bin(num).count("1")
        cnt+=1
    return cnt+1
n=int(f.readline().strip())
s=f.readline().strip()
input_val=int(s,2)
input_one_count=s.count("1")
#Base value
zero_first=input_val%(input_one_count+1)
one_first=input_val%(input_one_count-1) if input_one_count>1 else 0
ans=0
for idx,emt in enumerate(s):
    p=n-idx-1
    if emt=="0": #inverted to "1"
        ans=cnt_func((zero_first+(pow(2,p,input_one_count+1)))%(input_one_count+1))
    else: #inverted to "0"
        if input_one_count>1:
            ans=cnt_func((one_first-(pow(2,p,input_one_count-1)))%(input_one_count-1))
        else:
            ans=0
    print(ans)
f.close()
def main():
    n, m = map(int, input().split())
    ab = [sorted(list(map(int, input().split()))) for _ in [0] * n]
    l = [0] * (n - 1)
    for i in range(m):
        a, b = ab[i]
        if a != 1:
            l[a-2]+=1
        l[b - 2] += 1
    l=[i%2 for i in l]
    if sum(l) > 0:
        print("NO")
    else:
        print("YES")
main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    ab = [sorted(list(map(int, input().split()))) for _ in [0] * m]
    l = [0] * (n - 1)
    for i in range(m):
        a, b = ab[i]
        if a != 1:
            l[a-2]+=1
        l[b - 2] += 1
    l=[i%2 for i in l]
    if sum(l) > 0:
        print("NO")
    else:
        print("YES")
main()
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
while len(lun)<k:
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

### FIXED CODE ###

#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
while len(lun)<k+1:#正の整数
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])
import sys

file_input = sys.stdin

n = int(file_input.readline())
m = int(file_input.readline())

adj_list = [[] for i in range(n + 1)]

for line in file_input:
    i, j = map(int, line.split())
    adj_list[i].append(j)

unvisited = [True] * (n + 1)

ans = []

def dfs(u):
    unvisited[u] = False
    for v in adj_list[u]:
        if unvisited[v]:
            dfs(v)
    ans.append(u)

for s in range(1, n + 1):
    if unvisited[s]:
        dfs(s)

ans.reverse()

print(*ans, sep = '\n')

# Check whether there is a Hamilton path
for s, t in zip(ans, ans[1:]):
    if t not in adj_list[s]:
        print(1)
        break
else:
    print(0)


### FIXED CODE ###

import sys

file_input = sys.stdin

n = int(file_input.readline())
m = int(file_input.readline())

adj_list = [[] for i in range(n + 1)]

indeg = [0] * (n + 1)

for line in file_input:
    i, j = map(int, line.split())
    adj_list[i].append(j)
    indeg[j] += 1

unvisited = [True] * (n + 1)

from collections import deque
q = deque()

ans = []

def bfs(s):
    q.append(s)
    unvisited[s] = False
    while q:
        u = q.popleft()
        ans.append(u)
        for v in adj_list[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and unvisited[v]:
                unvisited[v] = False
                q.append(v)

# Topological Sort
for s in range(1, n + 1):
    if indeg[s] == 0 and unvisited[s]:
        bfs(s)

print(*ans, sep = '\n')

# Check whether there is a Hamilton path
for s, t in zip(ans, ans[1:]):
    if t not in adj_list[s]:
        print(1)
        break
else:
    print(0)
n = int(input())
N = 1
while N**2 < n:
    N += 1
ans = [0] * n
for x in range(1,N+1):
    for y in range(1,N+1):
        for z in range(1,N+1):
            a = x**2+y**2+z**2 + x*y+y*z+z*x
            if a >= 20: continue
            if x==y==z: b = 1
            elif x==y or y==z or x==z: b = 3
            else: b = 6
            ans[a-1] =b
            break
for i in ans: print(i)

### FIXED CODE ###

n = int(input())
ans = [0] * n
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            a = x * x + y * y + z * z + x * y + x * z + y * z
            if a > n: continue
            ans[a-1] += 1
for i in ans: print(i)
import math

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

cntC = B // C - A // C + int(A % C == 0)
cntD = B // D - A // D + int(A % D == 0)

lcm = C * D // math.gcd(C, D)
cntCD = B // lcm - A // lcm + int(A % lcm == 0)

print((B - A + 1) - (cntC + cntD - cntCD))


### FIXED CODE ###

import fractions

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

cntC = B // C - A // C + int(A % C == 0)
cntD = B // D - A // D + int(A % D == 0)

lcm = C * D // fractions.gcd(C, D)
cntCD = B // lcm - A // lcm + int(A % lcm == 0)

print((B - A + 1) - (cntC + cntD - cntCD))