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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(mid, s, suffix):
    # print(mid, s, suffix)
    for i in range(n - mid + 1):
        tmp = (s[i:i+mid], i)
        idx = bisect_left(suffix, tmp)

        # if mid == 4:
        #     print(tmp, idx)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tmp[0] == tgt[0][:mid]:
                if tgt[1] >= i + mid:
                    return True
                else:
                    idx += 1
                    if idx >= n:
                        flag = False
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    suffix.append((s[i:], i))

suffix.sort()

mn = 0
mx = n // 2 + 1
while(mx-mn>1):
    mid = (mx + mn) // 2
    is_succ = hantei(mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(mx, s, suffix):
    print(mx)
else:
    print(mn)

"""
17
aaaaaaaaaaaaaaaaa -> 8
10
absoabsoab -> 4
6
abcabc -> 3
10
abcdefghij -> 0
15
rangerangerange -> 5
2
xx -> 1
2
xy -> 0
12
abcdxxxxabcd -> 4

14
abcxxxxxxxxabc
3????????????????
"""

### FIXED CODE ###

import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


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

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

bit_to_i = {1<<i:i for i in range(N)}
  
dp = [0] * (1<<N)
dp[0] = 1

for n in range(1,1<<N):
    m = n
    xs = []
    while m:
        x = m&(-m)
        xs.append(x)
        m -= x
    k = len(xs)
    dp[n] = sum(dp[n-x] for x in xs if A[k-1][bit_to_i[x]]) % MOD

answer = dp[-1]
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

bit_count = [0]
for _ in range(N):
    bit_count += [x+1 for x in bit_count]
    
dp = [0] * (1<<N)
dp[0] = 1

for i in range((1<<N)-1):
    k = bit_count[i]
    for c in range(N):
        if A[k][c]:
            dp[(1<<c)^i] += dp[i]

answer = dp[-1] % MOD
print(answer)
### BUGGY CODE ###

import collections
N = int(input())
S = list(input())
cnt = []

for i in range(0,N-1):
    e = S[0:i].count('W')
    w = S[i+1:].count('E')
    cnt.append(e+w)
print(min(cnt))
    

### FIXED CODE ###

import collections
N = int(input())
S = list(input())
cnt = 0

ans = [0]*N

for i in range(1,N):
    if S[i] == "E":
        cnt += 1
ans[0] = cnt

for i in range(1,N):
    if S[i-1] == 'E' and S[i] == 'E':
        ans[i] = ans[i-1]-1
    elif S[i-1] == "W" and S[i] == 'W':
        ans[i] = ans[i-1]+1
    else:
        ans[i] = ans[i-1]
     
print(min(ans))
### BUGGY CODE ###

K, S = map(int,input().split())
p = 0
for x in range(K+1):
    if x > S:
        break
    for y in range(K+1):
        if x + y > S:
            break
        for z in range(K+1):
            if x + y + z == S:
                p += 1
            if x + y + z > S:
                break
print(p)

### FIXED CODE ###

K, S = map(int,input().split())
p = 0
for x in range(K+1):
    if S-x <= 2*K:
        for y in range(min(S-x+1,K+1)):
            if S-x-y <= K:
                p += 1
print(p)
### BUGGY CODE ###

 # -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

def main():
	N, W = map(int, input().split(" "))
	#goods = []
	#for _ in range(N):
		#w, v = map(int, input().split(" "))
		#goods.append((w, v))
		
	DP = [[0] * (W+2) for _ in range(N+1)]
	for i in range(N):
		#w, v = goods[i]
		w, v = map(int, input().split(" "))
		for w_sum in range(W+1):
			DP[i+1][w_sum] = max(DP[i+1][w_sum], DP[i][w_sum])
			if w_sum - w >= 0:
				DP[i+1][w_sum] = max(DP[i+1][w_sum], DP[i][w_sum - w] + v)
		
	print(DP[N][W])
		
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [0]*20001

for i in range(1, h + 1):
    ref = 10**10
    for a, b in l:
        temp = dp[i - a] + b
        ref = min(ref, temp)
    dp[i] = ref

print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [0]*20001

for i in range(1, h + 1):
    ref = 10**10
    for a, b in l:
        temp = dp[i - a] + b
        ref = min(ref, temp)
    dp[i] = ref

print(dp[h])
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

def main():
    s = ns()
    Q = ni()

    T1 = 0
    FrontS = ""
    BackS = ""
    for _ in range(Q):
        T = stdin.readline().split()
        if T[0] == "1":
            T1 += 1
        else:
            if T1 % 2 == 0:
                s = FrontS + s + BackS
                FrontS = ""
                BackS = ""

                if T[1] == "1":
                    FrontS = T[2] + FrontS
                else:
                    BackS += T[2]
            else:
                s = FrontS + s + BackS
                FrontS = ""
                BackS = ""
                
                if T[1] == "1":
                    BackS = T[2] + BackS
                else:
                    FrontS = T[2] + FrontS
    
    if BackS != "":
        s += BackS
    if FrontS != "":
        s = FrontS + s

    if T1 % 2 == 0:
        print(s)
    else:
        print(s[::-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def main():
    s = ns()
    Q = ni()

    T1 = 0
    FrontS = ""
    BackS = ""
    for _ in range(Q):
        T = stdin.readline().split()
        if T[0] == "1":
            FrontS, BackS = BackS, FrontS
            T1 += 1
        else:
            if T[1] == "1":
                FrontS += T[2]
            else:
                BackS += T[2]
                
    FrontS = FrontS[::-1]

    if T1 % 2 == 0:
        print(FrontS + s + BackS)
    else:
        print(FrontS + s[::-1] + BackS)

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

from itertools import permutations

def main():
    def floyd_warshall():
                for k in range(N):
                    for i in range(N):
                        for j in range(N):
                            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
                
    N, M, R = (int(i) for i in input().split())
    r = (int(i)-1 for i in input().split())
    res = float('inf')
    dist = [[float("inf")] * N for i in range(N)]
    
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        a -= 1
        b -= 1
        dist[a][b] = dist[b][a] = c
    
    floyd_warshall()
    for p in permutations(r):
            s = 0
            for i in range(R - 1):
                s += dist[p[i]][p[i + 1]]
            if s < res:
                res = s
    print(res)
main()
    

### FIXED CODE ###

import sys
from itertools import permutations

def read_int_list():
    return list(map(int, input().split()))

 
def main():
    def floyd_warshall():
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dd = d[i][k] + d[k][j]
                    if dd < d[i][j]:
                        d[i][j] = dd
 
    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(m):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)
 
 
main()
### BUGGY CODE ###

S = input()
T = str(S)

now_size = len(T)

while True:

    T = T.replace('01','')
    T = T.replace('10','')

    if now_size == len(T):
        break
    else:
        now_size = len(T)

print(len(S) - len(T))

### FIXED CODE ###

S = list(input())

original_length = len(S)

for i in range(len(S)-1, 0, -1):
    if len(S) > i:
        if S[i-1] != S[i]:
            del S[i-1:i+1]

print(original_length - len(S))
### BUGGY CODE ###

def main():
    q = int(input())
    
    
    def isPrime(n):
        if n == 1:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        m = int(n**0.5)+1
        for p in range(3, m, 2):
            if n % p == 0:
                return False
        return True
    
    
    ans = []
    for _ in range(q):
        l, r = map(int, input().split())
        cnt = 0
        for i in range(l, r+1, 2):
            if isPrime(i) and isPrime((i+1)//2):
                cnt += 1
        ans.append(cnt)
    
    for i in range(q):
        print(ans[i])

main()

### FIXED CODE ###

n_max = 10 ** 5 + 10
sieve = [0, 0] + [1]*n_max
m = 2
while m * m <= n_max:
    if sieve[m]:
        for n in range(2*m, n_max, m):
            sieve[n] = 0
    m += 1

ok = [0]*n_max
cums = [0]
for n in range(n_max):
    if sieve[n] and sieve[(n+1)//2]:
        ok[n] = 1
    cums.append(cums[-1]+ok[n])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cums[r+1]-cums[l])
### BUGGY CODE ###

import copy

n=int(input())
s=[input() for i in range(n)]

ssort=[]


for i in range(n):
  a=s[i]
  b=sorted(a)
  ssort.append(b)

tsort=copy.copy(ssort)

cnt=0

for i in tsort:
  for j in ssort:
    if i==j:
      cnt+=1

print((cnt-n)//2)

### FIXED CODE ###

import collections
n=int(input())
s=[]
a=0

for i in range(n):
    b=list(input())
    b.sort()
    b=str(b)
    s.append(b)

c=collections.Counter(s)

for i in c.values():
    if i>1:
        a+=i*(i-1)//2

print(a)
### BUGGY CODE ###

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

cnt = 0
while True:
  if 1 in map(lambda x: x % 2, li):
    break
  else:
    cnt += 1
    li = map(lambda x: x / 2, li)
print(cnt)


### FIXED CODE ###

def main():
    N = int(input())
    li = list(map(int, input().split()))

    num_of_operation = 0
    is_dividable = True

    while True:
        for num in li:
            if num % 2 != 0:
                is_dividable = False
                break

        if not is_dividable:
            break

        for i in range(N):
            li[i] //= 2
        num_of_operation += 1

    print(num_of_operation)


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

import math
K = int(input())
total = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            total+=math.gcd(math.gcd(a,b),c)
print(total)

### FIXED CODE ###

import math
K = int(input())
total = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            total+=math.gcd(math.gcd(a,b),c)
print(total)
### BUGGY CODE ###

INF = 10**9
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N): dp[i|open_bit] = min(dp[i|open_bit], dp[i] + a)
print(dp[-1] if dp[-1] != INF else -1)

### FIXED CODE ###

def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dp = [INF for _ in range(2**N)]
    dp[0] = 0
    for i in range(M):
        a, _ = map(int, input().split())
        *C, = map(int, input().split())
        open_bit = 0
        for i in C: open_bit |= 1 << i-1
        for i in range(2**N): dp[i|open_bit] = min(dp[i|open_bit], dp[i] + a)
    print(dp[-1] if dp[-1] != INF else -1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections

def nCr(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

n = int(input())
li = list(map(int,input().split()))

for i in range(n):
    li_a = li.copy()
    del li_a[i]
    c = collections.Counter(li_a)
    s = list(set(li_a))
    ans = 0
    # print(c)
    # print(c[s[1]])
    # print(s)
    
    for j in range(len(s)):
        if c[s[j]] <= 1:
            continue
        ans += nCr(c[s[j]], 2)
        
    print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))

ans_li = [0]*(n+10)

for i in li:
    ans_li[i] += 1
    
result = 0    
for i in ans_li:
    result += (i * (i-1)) // 2
    
for i in li:
    ans = result
    ans += ((ans_li[i] - 1) * (ans_li[i] - 2)) // 2- (ans_li[i] * (ans_li[i] - 1)) // 2
    print(ans)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
        x = i
        while x <= N:
            f[x] = 0
            x += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
            x = i
            while x <= N:
                f[x] = 0
                x += i
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
            x = i
            while x <= N:
                f[x] = 0
                x += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import math

n=int(input())
k=0
for i in range(int(math.sqrt(n))):
    while (i+1)**2 < n:
        k+=1
print((k+1)**2)


### FIXED CODE ###

n=int(input())
print((int(n**0.5))**2)
### BUGGY CODE ###

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()
cnt = 0
for j in B:
    a_index = bisect.bisect_left(A, j)
    c_index = bisect.bisect_right(C, j)
    cnt += len(A[:a_index])*len(C[c_index:])
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


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()
cnt = 0
for j in B:
    a_index = bisect.bisect_left(A, j)
    c_index = bisect.bisect_right(C, j)
    cnt += a_index*(N-c_index)
print(cnt)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():
    def read_tree(n):
        tree = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in stdin.readline().split()]
            tree[a].append(b)
        return tree

    def walk(p, x):
        cnt[p] += x
        for n in tree[p]:
            walk(n, x)

    n, q = [int(x) for x in input().split()]

    tree = read_tree(n)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in stdin.readline().split()]
        walk(p, x)

    for i in range(1, n + 1):
        print(cnt[i], end=" ")


main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():
    def read_tree(n):
        parents = [0 for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in input().split()]
            parents[b] = a
        return parents

    n, q = [int(x) for x in input().split()]

    parents = read_tree(n)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in input().split()]
        cnt[p] += x
    
    for i in range(1, n + 1):
        cnt[i] += cnt[parents[i]]

    for i in range(1, n + 1):
        print(cnt[i], end=" ")


main()
### BUGGY CODE ###

_s = str(input())

l_arr = _s.split("L")
r_arr = _s.split("R")
l_max = max([len(x) for x in l_arr])
r_max = max([len(x) for x in r_arr])
t = max(l_max, r_max)
if t % 2 != 0:
    t -= 1

s = list(_s)

lg = len(s)
arr = [1 for i in range(lg)]

for i in range(t):
    next_arr = [0 for i in range(lg)]
    for j in range(lg):
        cmd = s[j]
        curr = arr[j]
        if cmd == "L":
            next_arr[j - 1] += curr
        else:
            next_arr[j + 1] += curr
    arr = next_arr
    
print(" ".join(map(str, arr)))

### FIXED CODE ###

s = list(str(input()))
n = len(s)
ans = [0] * n
for ri in range(2):
    cnt = 0
    for i in range(n):
        if s[i] == "R":
            cnt += 1
        else:
            ans[i] += cnt // 2
            ans[i - 1] += (cnt + 1) // 2
            cnt = 0

    s.reverse()
    ans.reverse()
    for i in range(n):
        if s[i] == "L":
            s[i] = "R"
        else:
            s[i] = "L"

print(" ".join(map(str, ans)))
### BUGGY CODE ###

from collections import Counter as ct
emptylists=[]
allsums=0

n=int(input())
for s in range(n):
    something=dict(ct(str(input())))
    emptylists.append(something)

for x in range(n):
    for y in range(n):
        if emptylists[x]==emptylists[y]:
            allsums+=1
        else:
            continue
print(int((allsums-n)/2))

### FIXED CODE ###

n=int(input())
dicts={}
nums=0
for x in range(n):
    s=str(input())
    sorting=sorted(s)
    sorting="".join(sorting)
    if sorting not in dicts.keys():
        dicts[sorting]=1
    else:
        dicts[sorting]+=1
for x in  dicts.values():
    nums+=int(x*(x-1)/2)
print(nums)
### BUGGY CODE ###

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

def f(b,n) :
    r = 0
    i = 1
    while n:
        j = n % b
        r += j
        n = (n-j)//b
    return r


if n < s or (n // 2)+1 < s < n or( n // 3 ) + 2 < s < n//2:
    print("-1")
elif s == n:
    print(n+1)
elif s == 1:
    def check(n,b):
        while 1 < n :
            if n % b != 0:
                break
            n //= b
        if n == 1:
            return b
        return 0
    for b in range(2,int(n**0.5)+2):
        r = check(n,b)
        if r:
            print(r)
            exit()
    print(n)
else:
    for b in range(2,(n//2)+2):
        if f(b,n) == s:
            print(b)
            exit()
    print(n-s+1)


### FIXED CODE ###

n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b
if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
else:
    for b in range(2,rtn+1):
        if f(b,n) == s:
            print(b)
            exit()
    for p in range(rtn,0,-1):
        if (n-s) % p == 0:
            b = (n-s)//p + 1
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N):
  print(A[i-1:N].count(i))
print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = [0]*N
for i in range(1,N):
  l[A[i-1]-1] += 1
for i in range(N):
  print(l[i])
### BUGGY CODE ###

import numpy as np
n, m, k = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]
B = [int(n) for n in input().split()]

A = [a for a in np.cumsum([0] + A) if a <= k]
B = [b for b in np.cumsum([0] + B) if b <= k]
n_read = 0
for i, a in enumerate(A):
    if B[-1] + a > k:
        for j, b in enumerate(B[::-1]):
            if a + b <= k:
                n_read = max(n_read,  i + len(B) - j - 1)
                break
    else:
        n_read = max(n_read, i + len(B) - 1)
print(n_read)


### FIXED CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
l = len(B) - 1
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B[l::-1]):
        if a + b <= k:
            l -= j
            n_read = max(n_read, i + l)
            break
print(n_read)