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

from fractions import gcd

def solve(p, q, a, n, l=1):
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = max(l, int(q/p))
    p_denom = denom*p
    while n*q >= p_denom and denom <= a:  #n/denom >= p/q:
        p_, q_ = p_denom-q, q*denom
        if p_ <= 0:
            denom += 1
            p_denom += p
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)
        denom += 1
        p_denom += p
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))



### FIXED CODE ###

from fractions import gcd

def solve(p, q, a, n, l=1):
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = max(l, q//p)
    p_denom = denom*p
    while n*q >= p_denom and denom <= a:  #n/denom >= p/q:
        p_, q_ = p_denom-q, q*denom
        if p_ <= 0:
            denom += 1
            p_denom += p
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)
        denom += 1
        p_denom += p
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))
### BUGGY CODE ###

h, w, m = map(int, input().split())
dpcol = [0]*w
dprow = [0]*h
ypos = []
xpos = []
anscol = 0
ansrow = 0
ans = 0
hw = [list(map(lambda x: int(x) - 1, input().split())) for i in range(m)]

for i, j in hw:
    dpcol[j] += 1
    dprow[i] += 1

for i in range(w): #列の最大値
    if dpcol[i] > anscol:
        anscol = dpcol[i]
        xpos = [i]
    elif dpcol[i] == anscol:
        xpos.append(i)

for i in range(h):
    if dprow[i] > ansrow:
        ansrow = dprow[i]
        ypos = [i]
    elif dprow[i] == ansrow:
        ypos.append(i)

for i in ypos:
    for j in xpos:
        if [i, j] in hw:
            ans = anscol + ansrow - 1
        else:
            ans = anscol + ansrow
            print(ans)
            exit()
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
col = [0]*w
row = [0]*h
ypos = []
xpos = []
bomb = []

for i in range(m):
    H, W = map(lambda x: int(x) - 1, input().split())
    col[W] += 1
    row[H] += 1
    bomb.append((H, W))

maxcol = max(col)
maxrow = max(row)

xpos = [h for h, x in enumerate(col) if x == maxcol]
ypos = [w for w, y in enumerate(row) if y == maxrow]

ans = maxcol + maxrow - 1
bomb = set(bomb)

for i in ypos:
    for j in xpos:
        if (i, j) not in bomb:
            ans += 1
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
if __name__ == '__main__':
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        uf.union(a, b)

    print(len(list(uf.all_group_members().values()))-1)


### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
if __name__ == '__main__':
    input = sys.stdin.readline
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        uf.union(a, b)

    print(uf.group_count()-1)
### BUGGY CODE ###

N = int(input())
s = []
ans = 0
for i in range(N):
    s_i = ''.join(sorted(input()))
    if s_i in s:
        ans += s.count(s_i)
    s.append(s_i)

# s.sort()
# ans = 0
# print(s)
# for i in range(N):
#     for j in range(i+1, N):
#         if s[i] == s[j]:
#             ans += 1
#         elif s[i] < s[j]:
#             print(s[i], s[j])
#             break
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
s = []
for i in range(N):
    s_i = ''.join(sorted(input()))
    s.append(s_i)

s.sort()
ans = 0
for i in range(N):
    ans += bisect.bisect_right(s, s[i])-i-1
    # for j in range(i+1, N):
    #     if s[i] == s[j]:
    #         ans += 1
    #     elif s[i] < s[j]:
    #         break
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce

n, a, b = map(int, input().split())

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    return over // under

mod = 10**9+7

ans = ((1 << n) % mod -1 - cmb(n, a) % mod - cmb(n, b) % mod) % mod

print(ans)


### FIXED CODE ###

def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

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

import sys
N = int(input())
C = [0]
#c = [int(sys.stdin.readline()) for i in range(N)]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    #print(c, i, C)
    if c == C[-1]:
        N -= 1
        continue
    else:
        C.append(c)

#C = C+c
ans = 1
dp = [0] * (N + 100)
color = [[]for i in range((2*(10**5)+100))]
dp[0] = 1

dp[1] = 1
color[C[1]].append(1)
for i in range(2, N+1):
    dp[i] = dp[i - 1]

    # dp[i]+=~~
    for col in reversed(color[C[i]]):
        #print(i, col-1)
        if i - col == 1:
            break
        else:
            dp[i] += dp[col-1]
    # forの最後でいい
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)

# print(dp)
print(dp[N])


# pypyで


### FIXED CODE ###

import sys
N = int(input())
C = [0]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)
dp = [0] * (N + 2)
dp[0] = 1
dp[1] = 1
cumsum = [0] * (2 * (10 ** 5) + 2)
cumsum[C[1]] = 1
for i in range(2, N+1):
    dp[i] = dp[i - 1] + cumsum[C[i]]
    cumsum[C[i]] += dp[i-1]
    dp[i] %= (10 ** 9 + 7)
print(dp[N])
### BUGGY CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
for i in range(62):
    temp = 1 << i
    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD

print(ans)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)
### BUGGY CODE ###

from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    #始点sから各頂点への距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    d = [0] * node
    d[start] = 0
    #q:キュー(スタートからのコスト,頂点)
    #スタートをキューに入れる
    q = [(0,start)]
    while(len(q) != 0):
    #キューの先頭を取得
      ci, i = heappop(q)
    #キューの先頭から繋がっている頂点を探索
      for j in edge[i]:
        nc = ci + 1
        d[j] = nc
        heappush(q, (nc, j))
    return max(d)
#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

ans = 0
for i in range(N):
  ans = max(ans, dijkstra(i,N,E))


#出力
print(ans)

### FIXED CODE ###

import sys
from heapq import *
sys.setrecursionlimit(200000)

def rec(i):
  if dp[i] != 0:
    return dp[i]
  res = 0
  for j in E[i]:
    res = max(rec(j) + 1, res)
  dp[i] = res
  return dp[i]


#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]
dp = [0]*N

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

ans = 0
for i in range(N):
  ans = max(ans, rec(i))

#出力
print(ans)
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10000000)


def count(N, X):
    cnt = sum(map(int, str(X))) + sum(map(int, str(X - N)))
    return cnt


def solve_naive_first(N):
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive(N), 1+solve_naive(p*10-N))


def solve_naive(N):
    if N < 10:
        return min(N, 10-N+1)
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive((N // p + 1) * p - N) + (N // p + 1), solve_naive(N % p) + N // p)


def solve(N):
    l = list(map(int, str(N)[::-1]))
    n_0, n_1 = 0, 1  # 0: その桁で処理, 1: 次の桁に1タス
    for i in l:
        if i == 9:
            n_0, n_1 = n_0 + i, min(n_0 + 10 - i, n_1 + 10 - i - 1)
        else:
            n_0, n_1 = min(n_0 + i, n_1 + i + 1), min(n_0 +
                                                      10 - i, n_1 + 10 - i - 1)
    return min(n_0, n_1+1)


if __name__ == '__main__':
    N = int(input())
    ans = solve(N)
    print(ans)


### FIXED CODE ###

import math


def count(N, X):
    cnt = sum(map(int, str(X))) + sum(map(int, str(X - N)))
    return cnt


def solve_naive_first(N):
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive(N), 1+solve_naive(p*10-N))


def solve_naive(N):
    if N < 10:
        return min(N, 10-N+1)
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive((N // p + 1) * p - N) + (N // p + 1), solve_naive(N % p) + N // p)


def solve(N):
    n_0, n_1 = 0, 1  # 0: その桁で処理, 1: 次の桁に1タス
    for i in N[::-1]:
        i = int(i)
        if i == 9:
            n_0, n_1 = n_0 + i, min(n_0 + 10 - i, n_1 + 10 - i - 1)
        else:
            n_0, n_1 = min(n_0 + i, n_1 + i + 1), min(n_0 +
                                                      10 - i, n_1 + 10 - i - 1)
    return min(n_0, n_1+1)


if __name__ == '__main__':
    N = input()
    ans = solve(N)
    print(ans)
### BUGGY CODE ###

S = input()

def count(s):
    count_bigger = s.count('<')
    count_smaller = s.count('>')
    max_count = max(count_bigger, count_smaller)
    return (count_bigger*(count_bigger-1))/2 + (count_smaller*(count_smaller-1))/2 + max_count

s_list = []
ss = ""
for i in range(len(S)):
    if i == len(S)-1:
        ss += S[i]
        s_list.append(ss)
    elif S[i] == ">" and S[i+1] == "<":
        ss += S[i]
        s_list.append(ss)
        ss = ""
    else:
        ss += S[i]
answer = 0
for s in s_list:
    answer += count(s)
print(int(answer))

### FIXED CODE ###

S = input()

def count(up, down):
    max_count = max(up, down)
    return (up * (up - 1)) / 2 + (
                down * (down - 1)) / 2 + max_count

up = 0
down = 0
answer = 0

for i in range(len(S)):
    if i == len(S) - 1:
        if S[i] == ">":
            down += 1
        elif S[i] == "<":
            up += 1
        answer += count(up, down)
        up = 0
        down = 0
    elif S[i] == ">" and S[i + 1] == "<":
        if S[i] == ">":
            down += 1
        elif S[i] == "<":
            up += 1
        answer += count(up, down)
        up = 0
        down = 0
    else:
        if S[i] == ">":
            down += 1
        elif S[i] == "<":
            up += 1
print(int(answer))
### BUGGY CODE ###

_ = input()
nums = list(map(int, input().split()))
ans = 1

for num in nums:
    ans *= num

print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

_ = input()
nums = list(map(int, input().split()))
ans = 1

if 0 in nums:
  ans = 0
 
for num in nums:
    if ans <= 10 ** 18:
        ans *= num
    else:
        break
 
print(ans if ans <= 10**18 else -1)
### BUGGY CODE ###

S = list(input())
rm = 0
while True:
    length = len(S)
    for i in range(length - 1):
        # print(S)
        # print(f"1){length} {i} {len(S)}")
        if (int(S[i]) + int(S[i+1])) == 1:
            rm += 2
            del(S[i:i+2])
            # print(f"2){length} {i} {len(S)} {S}")
            break
        else:
            i += 1
    # print(f"3){length} {i} {len(S)}")
    if length == len(S):
        break
    i = 0
print(rm)

### FIXED CODE ###

S = list(input())
zeros = sum([1 if int(x) == 0 else 0 for x in S])
ones = sum([1 if int(x) == 1 else 0 for x in S])

print(min(zeros, ones) << 1)
### BUGGY CODE ###

N, M = (int(i) for i in input().split(' '))
py=[]
p =[]

# 全都市を配列に代入
for i in range(M):
    p = [i]
    p.extend([int(j) for j in input().split(' ')])
    py.append(p)

# 全N個の県について調べる
Npy = []
for i in range(1,N+1):
    # 県i
    pyi = [j for j in py if j[1] == i] # 県iの市リスト
    pyi.sort(key=lambda x: x[2]) # 県iの市を生まれた年でソート
    l = len(pyi)
    cnt = 0
    for k in range(1,l+1):
        pyi[k-1][2] = k
    Npy.extend(pyi)

Npy.sort(key=lambda x: x[0])

for t in Npy:
    print('{0:0>6}{1:0>6}'.format(t[1],t[2]))
    

### FIXED CODE ###

N, M = (int(i) for i in input().split(' '))
py=[]
p =[]

# 全都市を配列に代入
for i in range(M):
    p = [i]
    p.extend([int(j) for j in input().split(' ')])
    py.append(p)

# 設立年で一度ソートする
py.sort(key = lambda x: x[2])
pcid = [1] * N # 各県の都市ID

for i in range(M):
    p = py[i][1] # 県ID
    py[i][2] = pcid[p-1]
    pcid[p-1] += 1

py.sort(key=lambda x:x[0])
for t in py:
    print('{0:0>6}{1:0>6}'.format(t[1],t[2]))
### BUGGY CODE ###

N,K = map(int,input().split(' '))
H = list(map(int,input().split(' ')))
dp = [0]*N

for i in range(1,N):
  x = max(0,i-K)
  dp[i] = min([dp[j] + abs(H[i] - H[j]) for j in range(x,i)])
  
print(dp[-1])


### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
H = np.array(list(map(int,input().split())))
dp = np.zeros(N,dtype=int)

for i in range(1,N):
  x = max(0,i-K)
  dp[i] = np.min(dp[x:i] + abs(H[x:i] - H[i]))

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

n = int(input())
s = [input() for i in range(n)]
for i in range(n):
	s[i] = ''.join(list(sorted(s[i])))
ns = sorted(s)
t=0
for i in range(n-1):
	for j in range(1,n-i):
		if ns[i]==ns[i+j]:
			t += 1
		else:
			break
	continue
print(t)

### FIXED CODE ###

import collections
import math

n = int(input())
s = [input() for i in range(n)]
for i in range(n):
	s[i] = ''.join(list(sorted(s[i])))
c = collections.Counter(s)
t = 0
for v in c.values():
	if v>1:
		t += math.factorial(v) // (math.factorial(v - 2) * math.factorial(2))
	else:
		continue
print(t)
### BUGGY CODE ###

def main():
    S = raw_input()
    T = raw_input()
    
    # dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
    dp = [[''] * (len(T) + 1) for i in range(len(S) + 1)]
    
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            if S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + S[i - 1]
            else:
                if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i][j - 1]
    
    print(dp[-1][-1])
    
main()


### FIXED CODE ###

S = input()
T = input()

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = ''
i, j = len(S), len(T)
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i, j = i - 1, j - 1
    elif dp[i][j - 1] > dp[i - 1][j]:
        j -= 1
    else:
        i -= 1

print(ans[::-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=['Vacant','Male', 'Female']
    left=n+1
    sr=input("0")
    while right-left>1:
        mid=(left-right)//2
        x=input(str(mid))
        if ((left-right)%2==0 and x!=sr) or (n2%2==1 and x==sr):
            left=mid
        else:
            right=mid
            sr=x
    print(str(right))


if __name__=='__main__':
    main()

### FIXED CODE ###

N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x
### BUGGY CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
num = 1
for i in range(n):
	num = num // fractions.gcd(num, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += (num//a[i])
print(ans%(10**9+7))

### FIXED CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
	l = l // fractions.gcd(l, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += l//a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
result = "YES"
for i in range(N):
    for j in range(N-i-1):
        if(A[i]== A[i+j+1]):
            result = "NO"
print(result)

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
result = "YES"
for i in range(N-1):
    if(A[i]== A[i+1]):
        result = "NO"
print(result)
### BUGGY CODE ###

def equation(a, b, c):
    D = (b**2 - 4*a*c) ** (1/2)
    x_1 = (-b + D) / (2 * a)
    x_2 = (-b - D) / (2 * a)

    return x_1, x_2



def main():
    N = int(input())

    for n in range(1, N+1):
        cnt = 0
        for y in range(1, n):
            for z in range(1, n):
                x_1, x_2 = equation(1, y+z, y**2 + y*z + z**2 - n)

                if isinstance(x_1, float):
                    x_1 = round(x_1, 5)
                    if x_1.is_integer() == True and x_1 >= 1:
                        cnt += 1

                if isinstance(x_2, float):
                    x_2 = round(x_2, 5)
                    if x_2.is_integer() == True and x_2 >= 1:
                        cnt += 1

        print(cnt)




if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline


import math

# def equation(a, b, c):
#     D = (b**2 - 4*a*c) ** (1/2)
#     x_1 = (-b + D) / (2 * a)
#     x_2 = (-b - D) / (2 * a)

#     return x_1, x_2



def main():
    n = int(input())

    ans = [0]*(n+1)

    for x in range(1, int(math.sqrt(n))):
        for y in range(1, int(math.sqrt(n))):
            for z in range(1, int(math.sqrt(n))):

                e = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if e >= 1 and e <= n:
                    ans[int(e)] += 1

    for i in range(len(ans)-1):
        print(ans[i+1])




                # x_1, x_2 = equation(1, y+z, y**2 + y*z + z**2 - n)

                # if isinstance(x_1, float):
                #     x_1 = round(x_1, 5)
                #     if x_1.is_integer() == True and x_1 >= 1:
                #         cnt += 1

                # if isinstance(x_2, float):
                #     x_2 = round(x_2, 5)
                #     if x_2.is_integer() == True and x_2 >= 1:
                #         cnt += 1

        # print(cnt)




if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
sum_p = []
for i in p:
    sum_p.append((1 + i) / 2)

ans=[]
for i in range(n - k + 1):
    ans.append(sum(sum_p[i:i + k]))

print(max(ans))

### FIXED CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
sum_p = []
for i in p:
    sum_p.append((1 + i) / 2)

ans = sum(sum_p[0:k])
check = sum(sum_p[0:k])
p = 0
for i in range(k,n):
    check = check + sum_p[i] - sum_p[i - k]
    if check > ans:
        ans = check
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
print("Yes")
for v in range(1,N): 
    L = [el for el in G[v] if dist[el] + 1 == dist[v]]
    ans.append(L[0])
    print(L[0]+1)

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()