Ujan has been lazy lately, but now has decided to bring his yard to good shape. First, he decided to paint the path from his house to the gate.

The path consists of $n$ consecutive tiles, numbered from $1$ to $n$. Ujan will paint each tile in some color. He will consider the path aesthetic if for any two different tiles with numbers $i$ and $j$, such that $|j - i|$ is a divisor of $n$ greater than $1$, they have the same color. Formally, the colors of two tiles with numbers $i$ and $j$ should be the same if $|i-j| > 1$ and $n \bmod |i-j| = 0$ (where $x \bmod y$ is the remainder when dividing $x$ by $y$).

Ujan wants to brighten up space. What is the maximum number of different colors that Ujan can use, so that the path is aesthetic?


-----Input-----

The first line of input contains a single integer $n$ ($1 \leq n \leq 10^{12}$), the length of the path.


-----Output-----

Output a single integer, the maximum possible number of colors that the path can be painted in.


-----Examples-----
Input
4

Output
2

Input
5

Output
5



-----Note-----

In the first sample, two colors is the maximum number. Tiles $1$ and $3$ should have the same color since $4 \bmod |3-1| = 0$. Also, tiles $2$ and $4$ should have the same color since $4 \bmod |4-2| = 0$.

In the second sample, all five colors can be used. [Image]

Difficulty: competition

Starter code:

Solutions:
n = int(input())
p = 2
while n % p and p ** 2 <= n:
    p += 1
if p ** 2 > n:
    p = n
pw = n.bit_length() // p.bit_length()
while pow(p, pw) < n:
    pw += 1
while pow(p, pw) > n:
    pw -= 1
if pow(p, pw) == n:
    print(p)
else:
    print(1)


import sys
input = sys.stdin.readline

x=int(input())

if x==1:
    print(1)
    return

import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1

if len(FACT)>1:
    print(1)
else:
    print(list(FACT.keys())[0])


n = int(input())

test = 2
out = 1
while test * test <= n:
    p = 0
    while n % test == 0:
        n //= test
        p += 1

    if p >= 1:
        out = test
        break

    test += 1

if out == 1 and n > 1:
    print(n)
elif out > 1 and n == 1:
    print(out)
else:
    print(1)


from functools import reduce
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)


def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)
def gcd_mult(numbers):
    return reduce(gcd, numbers)


N = int(input())
dv = divisors(N)[1:-1]
if len(dv) == 0:
    print(N)
else:
    print(gcd_mult(dv))


3

import array
import bisect
import collections
from fractions import Fraction
import functools
import itertools
import math
import os
import sys


def main():
    N = read_int()
    print(solve(N))


def solve(N):
    d = []
    x = 2
    while x * x <= N:
        if N % x == 0:
            d.append(x)
            if x * x < N:
                d.append(N // x)
        x += 1

    d.sort()
    if not d:
        return N
    g = d[0]
    for x in d[1:]:
        g = math.gcd(g, x)
    return g


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def __starting_point():
    main()

__starting_point()

import sys
readline = sys.stdin.readline
def prf(m):
    pf = {}
    for i in range(2, int(m**0.5)+1):
        while m % i == 0:
            pf[i] = pf.get(i, 0)+1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf

N = int(readline())

Pf = prf(N)

ans = 1
if len(Pf) == 1:
    ans = list(Pf.keys())[0]

print(ans)              


n = int(input())
some_pow = False
prime = True
d = 2
while d * d <= n:
    if n % d == 0:
        tst = n
        while tst % d == 0 and tst > 1:
            tst //= d
        if tst == 1:
            some_pow = True
        prime = False
        break
    d += 1
if prime:
    print(n)
elif some_pow:
    print(d)
else:
    print(1)


from math import sqrt, floor

def sieve(n):
	primes = [True] * (n + 1)
	primes[0] = False
	primes[1] = False
	for i in range(2, n + 1):
		if i*i > n:
			break

		# if primes[i] == True:
		if primes[i] == False:
			continue

		# for j in range(2*i, n + 1):
		for j in range(2*i, n + 1, i):
			# if j == 5:
			# 	print('i: ', i)
			primes[j] = False

	return primes


def run_testcase():
	number = int(input())

	# print(sieve(number))
	# print(zip(range(number), sieve(number)))
	# print(list(zip(range(number), sieve(number))))
	# print(list(zip(range(number + 1), sieve(number))))

	# prime_divisors_count = 0

	# # while number % 2 == 0:
	# # 	prime_divisors_count += 1

	# last_prime_divisor = 2


	# # def sieve():


	# if number % last_prime_divisor == 0:
	# 	prime_divisors_count += 1
	# 	while number % last_prime_divisor == 0:
	# 		# number /= last_prime_divisor
	# 		number = number // last_prime_divisor

	# num_sqrt = sqrt(number)

	# # primes = [True] * (int(sqrt) + 1)
	# # primes = [True] * int(sqrt)
	# # primes = [True] * (int(sqrt) + 1)
	# # primes = [True] * (floor(num_sqrt) + 1)
	# primes = [True] * (floor(num_sqrt) + 2)
	# primes[0] = False
	# primes[1] = False

	# # print(len(primes))

	# # for i in range(len(primes)):
	# # for i in range(len(2, primes)):
	# for i in range(2, len(primes)):
	# 	# for j in range(i)
	# 	if i*i >= num_sqrt:
	# 		break

	# 	# if prime[i] == True:
	# 	if primes[i] == True:
	# 		continue

	# 	# j = 0
	# 	j = 2 * i
	# 	while j < len(primes):
	# 		# print(j)
	# 		primes[j] = False
	# 		j += i

		# print('test')

	num_sqrt = sqrt(number)

	# primes = sieve(num_sqrt)
	primes = sieve(floor(num_sqrt))

	prime_divisors_count = 0
	last_prime_divisor = 0

	for value, prime in enumerate(primes):
		if prime:
			if number % value == 0:
				last_prime_divisor = value
				prime_divisors_count += 1
				if prime_divisors_count >= 2:
					return 1
				while number % value == 0:
					number = number // value
				if number == 1:
					return value
				else:
					return 1



	# for value, prime in primes:
	for value, prime in enumerate(primes):
		if prime:
			# print(value)
			if number % value == 0:
				last_prime_divisor = value
				prime_divisors_count += 1
				if prime_divisors_count >= 2:
					return 1


	# return last_prime_divisor
	# return last_prime_divisor if last_prime_divisor != 0 else number

	# print(last_prime_divisor)

	# if number == 2:
	# 	return 2

	# if last_prime_divisor ** 2 == number:
		# return last_prime_divisor
	if last_prime_divisor == 0:
		return number
	elif last_prime_divisor ** 2 == number:
		return last_prime_divisor
	else:
		return 1

	return last_prime_divisor if last_prime_divisor != 0 else number

# testcase_count = int(input())

# for i in range(testcase_count):
# 	print(str(run_testcase()))
	# run_testcase()
# run_testcase()
print(str(run_testcase()))


"""  if need to find numbers 1...n such that n% (|i-j|>1)>0, can solv as p^k, p is prim num & answr or belw process"""

while True:
    try:
        n = int(input())
        num, i = [], 2
        if n== 1:
            print("1")
            continue
        while i*i <= n:
            if n%i == 0:
                num.append(i)
                while n%i == 0:n/=i
            i+=1
        if n>1:num.append(n)
        if len(num)>1:print(1)
        else:print(num[0])
            
    except EOFError:
        break

from math import gcd
n = int(input())
if n == 1:
    print(1)
    return
elif n == 2:
    print(2)
    return
d = 0
for i in range(2, n):
    if i * i > n:
        break
    if n % i:
        continue
    d = gcd(d, i)
    d = gcd(d, n // i)
if d:
    print(d)
else:
    print(n)


from math import ceil
def find_divisor(n):
    if n == 2:
        return []
    root = ceil(n ** 0.5)
    ans = []
    for i in range(2, root + 1):
        if n % i == 0:
            ans.extend([i, n / i])

    return list(set(ans))

def fans(n):
    div = find_divisor(n)
    if len(div) == 0:
        return n
    else:
        m = min(div)
        divs = True
        for x in div:
            divs = divs and (x % m == 0)
            if divs == False:
                break
        
        if divs: 
            return min(div)
        else:
            return 1

def __starting_point():
    n = int(input())
    print(fans(n))



__starting_point()

from math import gcd
n = int(input())
if n == 1:
    print(1)
    return
elif n == 2:
    print(2)
    return
else:
    d = 0
    for i in range(2, n):
        if i * i > n:
            break
        if (n % i)==0:
        
           d = gcd(d, i)
           d = gcd(d, n // i)
if d:
    print(d)
else:
    print(n)


import math

def IsPrime(x):
    if x<=2: return x==2
    top = int(math.sqrt(x))+1
    for i in range(2,top):
        if x%i==0:
            return False
    return True

val = int(input())
if val==1: print('1')
elif IsPrime(val): print(val)
else:
    cnt = 0
    top = int(math.sqrt(val))+1
    for i in range(2,top):
        if val%i==0:
            cnt += 1
            while val%i==0:
                val /= i
            if val==1:
                print(i)
            else: print('1')
            return


from math import sqrt, ceil

def mindiv(n):
    if n==1: return 1
    if n%2==0: return 2
    if n%3==0: return 3
    div,inc=5,2
    while div<ceil(sqrt(n))+1:
        if n%div == 0: return div
        div+=inc
        inc=6-inc
    return n
n=int(input())
m=mindiv(n)
while n%m==0 and n>m: n=n/m
print(1 if n>m else m)


# #n14 = 951069502319
# n = int(input())

# def isprime(n):
#     for i in range(2,int(n**0.5)+1):
#         if n%i==0:
#             return False
#     return True
# FOUND = -1

# x = int(n**0.5)
# if x*x == n:
#     n = x

# if not isprime(n):
#     for i in range(2, int(n**0.5)+1):
#         if isprime(i) and n%i==0:    
#             FOUND = i
#             break
#     # print (FOUND)
#     if FOUND != -1:
#         while(n % FOUND == 0):
#             n /= FOUND
#         if n == 1:
#             print (FOUND)
#         else:
#             print (1)
# else:
#     print (n)

n = int(input())

check = 0

for i in range(2,int(n**0.5)+1):
    if n%i==0:
        #khong phai snt
        check = 1
        while n%i==0:
            n /= i
        if n == 1:
            print (i)
            break
        else:
            print(1)
            break

if check == 0:
    print (n)


import math
from sys import stdin
	
def factorize(x):
	i = 2
	y = x
	prime_factors = []
	while i * i <= x:
		if y % i == 0:
			prime_factors.append(i)
			while y % i == 0:
				y //= i
		i += 1
	if y > 1:
		prime_factors.append(y)
	return prime_factors

def main():
	n = int(input())
	prime_factors = factorize(n)
	
	if n == 1 or len(prime_factors) > 1:
		print(1)
	elif n > prime_factors[0]:
		print(prime_factors[0])
	else:
		print(n)

def __starting_point():
	main()
__starting_point()

n = int(input())

def isPrime(val):
    if(val <2):
        return 0
    n = int(val**0.5)+1
    for i in range(2,n):
        if (val%i) ==0:
            return 0
    return val

def titlePaint(n):
    if n < 2 or isPrime(n):
        print(n)
        return 0
    n1 = int(n**0.5)*2
    prime =[]
    dic = dict()
    for i in range(2,n1):
        while n%i==0:
            prime.append(i)
            if i not in dic:
                dic[i] = 1
            else:
                dic[i]+=1
            n/=i
    dic1 = sorted(list(dic.items()), key=lambda x: x[1])
    if dic1[0][1] ==1:
        print(1)
        return 0
    if not dic:
        print(1)
        return 0
    if len(dic) ==1:
        print(dic1[0][0])
        return 0
    else:
        print(1)
        return 0
titlePaint(n)


n = int(input())

def isPrime(val):
    if(val <2):
        return 0
    n = int(val**0.5)+1
    for i in range(2,n):
        if (val%i) ==0:
            return 0
    return val

def titlePaint(n):
    if n < 2 or isPrime(n):
        print(n)
        return 0
    n1 = int(n**0.5)*2
    dic = dict()
    for i in range(2,n1):
        while n%i==0:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i]+=1
            n/=i
    dic1 = sorted(list(dic.items()), key=lambda x: x[1])
    if dic1[0][1] ==1:
        print(1)
        return 0
    if not dic:
        print(1)
        return 0
    if len(dic) ==1:
        print(dic1[0][0])
        return 0
    else:
        print(1)
        return 0
titlePaint(n)


n = int(input())

def isPrime(val):
    if(val <2):
        return 0
    n = int(val**0.5)+1
    for i in range(2,n):
        if (val%i) ==0:
            return 0
    return 1

def titlePaint(n):
    if n < 2 or isPrime(n):
        print(n)
        return 0
    n1 = int(n**0.5)*2
    dic = dict()
    for i in range(2,n1):
        while n%i==0:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i]+=1
            n/=i
    dic1 = sorted(list(dic.items()), key=lambda x: x[1])
    if dic1[0][1] ==1:
        print(1)
        return 0
    if not dic:
        print(1)
        return 0
    if len(dic) ==1:
        print(dic1[0][0])
        return 0
    else:
        print(1)
        return 0
titlePaint(n)


from math import sqrt,gcd


def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    #
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            #
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiples of its witnesses to prepare for larger
            # numbers
            #
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1


def is_prime(n):
    if n<=1:
        return False
    if n == 2:
        return True
    if n % 2 ==0:
        return False
    return all(n%i for i in range(3,int(sqrt(n))+1))


def calculate_colors(n):
    primes = gen_primes()
    sqr_n = int(sqrt(n)) + 1
    if n == 1:
        return 1
    for p in primes:
        if n % p == 0:
            while n % p == 0:
                g= gcd(p,n)
                n = int(n//g)
            if n > 1:
                return 1
            else:
                return p
        if p > sqr_n:
            return n



n = int(input())
print(calculate_colors(n))

import math


def p(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return i
    else:
        return x


def r(x):
    if round(x) - x < 0.5:
        return round(x)
    else:
        return round(x) - 1


n = int(input())
if n == 1:
    print(1)
else:
    m = p(n)
    d = math.log(n, m)
    if m**r(d) == n:
        print(m)
    else:
        print(1)


import os, sys, math

n = int(input())
sqt = int(math.sqrt(n))

def IsPrime(n):
	for i in range(2,sqt+1):
		if n%i == 0:
			return False
	return True
if IsPrime(n):
	print(n)
	return

found = 0
for i in range(2,sqt+1):
	if n%i != 0: continue
	x = n/i
	while x%i == 0:
		x /= i
	if x == 1:
		print(i)
		return
	else:
		found += 1
		if found == 2:
			print(1)
			return
print(1)


import math
def smallestDivisor(n):
    # if divisible by 2
    if (n % 2 == 0):
        return 2;

        # iterate from 3 to sqrt(n)
    i = 3;
    while (i * i <= n):
        if (n % i == 0):
            return i;
        i += 2;
    return n;
def isPower(div,n):
    if n == 1:
        return True
    ans = int(math.log(n,div))
    if pow(div,ans) == n or pow(div,ans+1) == n:
        return True
    else:
        False
num = int(input().strip())
small = smallestDivisor(num)
if isPower(small,num):
    print(small)
else:
    print(1)


'''input
5
'''
from math import gcd

N = int(input())

ats = 0

i = 1

while i*i <= N:
	if N % i == 0:
		if i != 1: ats = gcd(ats, i)

		ats = gcd(ats, N // i)

	i += 1


print(ats)

import math

n = int(input())

if n == 1:
	print("1")
else:
	smallestDivisor = n
	if n % 2 == 0:
		smallestDivisor = 2
	elif n % 3 == 0:
		smallestDivisor = 3
	else:
		for i in range(5, int(math.sqrt(n)) + 1, 2):
			if n % i == 0:
				smallestDivisor = i
				break

	while n % smallestDivisor == 0:
		n //= smallestDivisor

	print(str(smallestDivisor) if n == 1 else "1")