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

N=int(input())
import math

for i in range(1,N+1):
    ans=0
    for x in range(1,33):
        for y in range(1,33):
            if x>=y:
                if x^2+y^2<1000:
                    a=-(3*(x*x)+3*(y*y)+2*x*y)/4+i
                    if a>0:
                        b=(math.sqrt(a)-(x+y)/2)
                        if b>0 and b%1==0.0:
                            if x==y:
                                ans+=1
                            else:
                                ans+=2

    print(ans)



### FIXED CODE ###

N=int(input())
li=[0]*N
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            temp=x**2+y**2+z**2+x*y+y*z+z*x
            if temp<=N:
                li[temp-1]+=1
for i in range(N):
    print(li[i])
### BUGGY CODE ###

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])

	divs = sum([(lcm//x)%2 for x in a])
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

from fractions import gcd
n, m = map(int, input().split())
a = list(map(int, input().split()))
m *= 2

if n == 1:
	print((m//a[0]+1)//2)
else:
	lcm = a[0]*a[1]//gcd(a[0], a[1])
	for i in range(2, n):
		lcm = lcm * a[i] // gcd(lcm, a[i])
		if lcm > m:
			print(0)
			sys.exit()

	divs = 0
	for x in a:
		divs += (lcm//x)%2
	if divs < n:
		print(0)
	else:
		print((m//lcm+1)//2)
### BUGGY CODE ###

#!/usr/bin/env python3
k = int(input())
if k % 2 < 1 or k % 5 < 0:
    print(-1)
else:
    c = len(str(k))
    mod = int("7" * c) % k
    while mod > 0:
        mod += pow(10, c, k) * 7
        mod %= k
        c += 1
    print(c)


### FIXED CODE ###

#!/usr/bin/env python3
k = int(input())
if k % 2 < 1 or k % 5 < 1:
    print(-1)
else:
    c = 1
    mod = 7 % k
    mop = 7 % k
    while mod > 0:
        mop = mop*10%k
        mod += mop
        mod %= k
        c += 1
    print(c)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
c = [False]*N
ans = 0
for i in range(N):
    if c[i]:
        continue
    if i == N-1 or A[i] != A[i+1]:
        ans += 1
    if i == N-1:
        break
    for j in range(i+1,N):
        if not c[j] and A[j]%A[i]==0:
            c[j] = True
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
B = [True]*(A[-1]+1)
i = 0
for i in range(N):
  if i < N-1 and A[i] == A[i+1]:
    B[A[i]] = False
  if A[-1] < 2*A[i]:
    continue
  M = A[-1]//A[i]+1
  for j in range(2,M):
    B[j*A[i]] = False

ans = 0
for a in A:
  if B[a]:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_right, bisect_left

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    T = [i + 1 - A[i] for i in range(N)]
    idx = sorted(range(N), key=lambda k: T[k])
    T.sort()

    ans = 0
    for i in range(N):
        target = A[i] + i + 1
        left = bisect_left(T, target)
        if left > N - 1:
            continue
        if T[left] != target:
            continue
        else:
            right = bisect_right(T, target)
            for k in range(left, min(right, N)):
                j = idx[k]
                if i < j:
                    ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_right, bisect_left

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    T = [i + 1 - A[i] for i in range(N)]
    idx = sorted(range(N), key=lambda k: T[k])
    T.sort()

    ans = 0
    for i in range(N):
        target = A[i] + i + 1
        left = bisect_left(T, target)
        if left > N - 1:
            continue
        if T[left] != target:
            continue
        else:
            right = bisect_right(T, target)
            ans += right - left
    print(ans)


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

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    count2 = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        tmp = count
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count == tmp : count2 += 1
        if count2 > 300 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import sys

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
#a = list(a)
#b = list(b)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if a[j] + i == m:
			l.append(b[j])
			count += 1
		else:
			break

	if len(l) != 0:
		maximum = max(l)
		ans += maximum
		l.pop(l.index(maximum))

print(ans)


### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

import heapq

q = int(input())

# 中央値との大小で集団を２つに分けて管理したいぞ
_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            # 最大ヒープ
            heapq.heappush(a_small, -a)
            total += abs(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            # 最小ヒープ
            heapq.heappush(a_large, a)
            total += abs(a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        # total = 0
        x = -a_small[0]
        # for small in a_small:
        #     total += abs(x+small)
        # for large in a_large:
        #     total += abs(x-large)
        print(x, total+cons)


        

### FIXED CODE ###

import heapq

q = int(input())

# 中央値との大小で集団を２つに分けて管理したいぞ
_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            # 最大ヒープ
            heapq.heappush(a_small, -a)
            total += -(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            # 最小ヒープ
            heapq.heappush(a_large, a)
            total += (a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        x = -a_small[0]
        print(x, total+cons)
### BUGGY CODE ###

n, k = map(int, input().split())
*H, = map(int, input().split())
DP = [0 for i in range(n)]
for i in range(1, n):
    DP[i] = min([DP[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(i, k)+1)])
print(DP[n-1])


### FIXED CODE ###

N, K = map(int, input().split())
K = min(N, K)
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])
### BUGGY CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int64)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int64)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    count=np.count_nonzero(A<Arr[j][1])
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=Arr[j][1]
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

# print(np.sum(A))

### FIXED CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int32)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int32)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    change_Num=Arr[j][1]
    count=np.count_nonzero(A<change_Num)
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=change_Num
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

# print(np.sum(A))
### BUGGY CODE ###

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
r = [[0]*w for _ in range(h)]
for i in range(h):
    flg = False
    row = s[i]
    row2 = r[i]
    for j in range(w):
        if row[j]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and row[j]=='#':
            for k in range(begin, j):
                row2[k] = tmp
            flg = False
    if flg:
        for k in range(begin, w):
            row2[k] = tmp
c = [[0]*w for _ in range(h)]
for i in range(w):
    flg = False
    for j in range(h):
        if s[j][i]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[j][i]=='#':
            for k in range(begin, j):
                c[k][i] = tmp
            flg = False
    if flg:
        for k in range(begin, h):
            c[k][i] = tmp
ans = 0
for row1, row2 in zip(r, c):
    for e1, e2 in zip(row1, row2):
        if ans<e1+e2-1:
            ans = e1+e2-1
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
r = [[0]*w for _ in range(h)]
for i in range(h):
    flg = False
    row = s[i]
    row2 = r[i]
    for j in range(w):
        if row[j]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and row[j]=='#':
            for k in range(begin, j):
                row2[k] = tmp
            flg = False
    if flg:
        for k in range(begin, w):
            row2[k] = tmp
c = [[0]*w for _ in range(h)]
for i in range(w):
    flg = False
    for j in range(h):
        if s[j][i]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[j][i]=='#':
            for k in range(begin, j):
                c[k][i] = tmp
            flg = False
    if flg:
        for k in range(begin, h):
            c[k][i] = tmp
ans = 0
for row1, row2 in zip(r, c):
    for e1, e2 in zip(row1, row2):
        if ans<e1+e2-1:
            ans = e1+e2-1
print(ans)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for i in range(len(C)):
    b = bisect.bisect_left(B,C[i])
    if b == 0:
        continue
    for j in range(b):
        a = bisect.bisect_left(A,B[j])
        ans += a
print(ans)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for b in B:
    a = bisect.bisect_left(A,b)
    c = n - bisect.bisect_left(C,b+1)
    ans += a*c
print(ans)
### BUGGY CODE ###

from collections import deque
def bfs(maze, visited, l):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if all ([-1 not in i for i in visited]):
            s=set()
            for i in visited:
                s=s|set(i)
            return(max(s))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])

print(bfs(maze, visited,l_b))

### FIXED CODE ###

from collections import deque
def bfs(maze, visited, l,n_w):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if n_w==0:
            s=set()
            tmp=0
            for i in visited:
                if max(i)>tmp:tmp=max(i)
            return(tmp)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                n_w-=1

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])
n_w=R*C-len(l_b)

print(bfs(maze, visited,l_b,n_w))
### BUGGY CODE ###

N=int(input())

l=0
r=N

print(l)
bstate=input()

while True:
    
    c=int((l+r)/2)+1
    #print(c,l,r)
    state=input()
    if state=="Vacant":
        break
    
    if state==bstate:
        l=c
    else:
        r=c



### FIXED CODE ###



N=int(input())

l=0
r=N

print(l,flush=True)
bstate=input()

if bstate!="Vacant":
    while True:
        #c=int((l+r)/2)
        L=int((r-l)/2)
        if (L%2)==0:
            L-=1
        c=l+L
        c=max(l+1,c)
        c=min(r-1,c)
        #print(c,l,r)
        print(c,flush=True)
        state=input()
        if state=="Vacant":
            break

        if state!=bstate:
            l=c
        else:
            r=c

        bstate=state
### BUGGY CODE ###

from collections import Counter

N, M=map(int, input().split())
m=[]
ans = 300

for i in range(N):
    m.append(list(map(int,input().split())))


def search(ln):
    l = []
    for r in m:
        for col in r:
            if col in ln:
                l.append(col)
                break
    s,c = Counter(l).most_common(1)[0]
    global ans
    if c < ans:
        ans = c
    ln.remove(s)
    if len(ln) == 0:
        return 
    search(ln)
search(list(range(1, M+1)))
print (ans)

### FIXED CODE ###

from collections import Counter

N, M=map(int, input().split())
m=[]
ans = 300

for i in range(N):
    m.append(list(map(int,input().split())))

def search(ln):
    #l = []
    cnt = Counter()
    for r in m:
        cnt[r[0]] += 1
    s,c = cnt.most_common(1)[0]
    global ans
    ans = min(ans, c)
    ln.remove(s)
    for r in m:
        r.remove(s)
    if len(ln) == 0:
        return 
    search(ln)
search(list(range(1, M+1)))
print (ans)
### BUGGY CODE ###

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        if s[h][w] == ".":
            l[h][w], d[h][w] = 1,1
            if w != 0: l[h][w] = l[h][w-1] + 1
            if h != 0: d[h][w] = d[h-1][w] + 1
        if s[H-1-h][W-1-w] == ".":
            r[H-1-h][W-1-w],u[H-1-h][W-1-w] = 1,1
            if w != 0: r[H-1-h][W-1-w] = r[H-1-h][W-w] + 1
            if h != 0: u[H-1-h][W-1-w] = u[H-h][W-1-w] + 1

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

print(ans)
        

### FIXED CODE ###

H,W = map(int,input().split())
s = [[] for i in range(H)]
for i in range(H): s[i] = list(input())
l = [[0]*W for i in range(H)]
r = [[0]*W for i in range(H)]
d = [[0]*W for i in range(H)]
u = [[0]*W for i in range(H)]

for h in range(H):
    if s[h][0] == ".": l[h][0] = 1
    for w in range(1,W):
        if s[h][w] == ".": l[h][w] = l[h][w-1] + 1
    if s[h][W-1] == ".": r[h][W-1] = 1
    for w in range(1,W):
        if s[h][W-1-w] == ".": r[h][W-1-w] = r[h][W-w] + 1

for w in range(W):
    if s[0][w] == ".": d[0][w] = 1
    for h in range(1,H):
        if s[h][w] == ".": d[h][w] = d[h-1][w] + 1
    if s[H-1][w] == ".": u[H-1][w] = 1
    for h in range(1,H):
        if s[H-1-h][w] == ".": u[H-1-h][w] = u[H-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, l[h][w]+r[h][w]+u[h][w]+d[h][w]-3)

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

N = int(input())
X = input()
    
cnt_1 = 0
for i in X:
    if i == '1':
        cnt_1 += 1

for i in range(N):
    if X[i] == '1':
        n = int(X, 2) - (1 << (N-i-1))
        tmp_cnt_1 = cnt_1 - 1
    else:
        n = int(X, 2) + (1 << (N-i-1))
        tmp_cnt_1 = cnt_1 + 1
        
    if n == 0:
        print(0)
        continue

    n = n % tmp_cnt_1
    cnt = 1

    while n != 0:
        c = 0
        for j in bin(n):
            c += j=='1'
        n = n % c
        cnt += 1
    print(cnt)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def pop_cnt(n):
    return bin(n).count('1')


def f(n):
    cnt = 0
    while n != 0:
        n = n % pop_cnt(n)
        cnt += 1
    return cnt
 
n = int(readline())
x2 = list(readline().decode().rstrip())
x10 = int(''.join(x2), 2)

c = x2.count('1')
mod1 = x10 % (c + 1)
mod2 = x10 % (c - 1) if c-1 != 0 else 0

for i in range(n):
    ans = 0
    if x2[i] == '0':
        t = (mod1 + pow(2, n-i-1, c+1)) % (c+1)
    else:
        if c-1 != 0:
            t = (mod2 - pow(2, n-i-1, c-1)) % (c-1)
        else:
            print(0)
            continue
    
    ans = f(t) + 1
    print(ans)