Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry.

He bought n pieces of jewelry. The i-th piece has price equal to i + 1, that is, the prices of the jewelry are 2, 3, 4, ... n + 1.

Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.

Help Sherlock complete this trivial task.


-----Input-----

The only line contains single integer n (1 ≤ n ≤ 100000) — the number of jewelry pieces.


-----Output-----

The first line of output should contain a single integer k, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.

The next line should consist of n space-separated integers (between 1 and k) that specify the color of each piece in the order of increasing price.

If there are multiple ways to color the pieces using k colors, you can output any of them.


-----Examples-----
Input
3

Output
2
1 1 2 
Input
4

Output
2
2 1 1 2



-----Note-----

In the first input, the colors for first, second and third pieces of jewelry having respective prices 2, 3 and 4 are 1, 1 and 2 respectively.

In this case, as 2 is a prime divisor of 4, colors of jewelry having prices 2 and 4 must be distinct.

Difficulty: competition

Starter code:

Solutions:
3
n = int(input())
a = [True] * (n + 2)
for i in range(2, n + 2):
    if not a[i]:
        continue
    j =  i * i
    while j < n + 2:
        a[j] = False
        j += i
if n <= 2:
    print(1)
else:
    print(2)
print(' '.join('1' if x else '2' for x in a[2:]))


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

n=int(input())
if n<=2:
    print(1)
    for i in range(n):
        print(1,end=' ')
else:
    print(2)
    for i in range(2,n+2):
        if isprime(i):
            print(1, end=' ')
        else:
            print(2,end=' ')


n = int(input())
if n == 2:
    print('1\n1 1')
elif n == 1:
    print('1\n1')
else:
    a = [True for i in range(n + 2)]
    for i in range(2, n + 2):
        if a[i]:
            for j in range(i * 2, n + 2, i):
                a[j] = False
    print(2, 1, sep = '\n', end = '')
    for i in range(1, n):
        print('', 2 - a[i + 2], end = '')


n = int(input())
if n <= 2:
    print(1)
    for i in range(n):
        print(1, end=' ')
else:
    prime = [1] * (n + 2)
    for i in range(2, n + 2):
        if prime[i]:
            k = i
            while k + i < n + 2:
                k += i
                prime[k] = 0
    print(2)
    for i in range(2, n + 2):
        if prime[i]:
            print(1, end=' ')
        else:
            print(2, end=' ')

n = int(input())
if n == 1:
    print(1)
    print(1)
elif n == 2:
    print(1)
    print('1 1')
else:
    print(2)
    ans = []

    def prime(q):
        j = 2
        while j * j <= q:
            if q % j == 0:
                return False
            j += 1
        return True

    for i in range(2, n + 2):
        if prime(i):
            ans.append('1')
        else:
            ans.append('2')
    print(' '.join(ans))


def is_prime(n):
	if n == 2 or n == 3: return True
	if n < 2 or n%2 == 0: return False
	if n < 9: return True
	if n%3 == 0: return False
	r = int(n**0.5)
	f = 5
	while f <= r:
		if n%f == 0: return False
		if n%(f+2) == 0: return False
		f +=6
	return True

n = int(input())

colors = []

for i in range(2, n + 2):
	if not is_prime(i):
		colors.append(str(2))
	else:
		colors.append(str(1))
		
if n >= 3:
	print(2)
else:
	print(1)

print(" ".join(colors))

n = int(input())
primes = [2]
primes_bool = [2 for _ in range(10**5+4)]
primes_bool[2] = 1
for i in range(3,10**5+4,2):
	isPrime = True
	for j in range(len(primes)):
		if(primes[j]**2 > i):
			break
		if(i % primes[j] == 0):
			isPrime = False
			break
	if(isPrime):
		primes.append(i)
		primes_bool[i] = 1


if(n <= 2):
	print(1)
else:
	print(2)

print(*primes_bool[2:(n+2)])

last = 1
n = int(input())
arr = [1]*(n + 2)
for i in range(2, n + 2):
    if arr[i] != 1:
        continue
    for j in range(2*i, n + 2, i):
        if arr[j] == arr[i]:
            arr[j] += 1
            last = max(last, arr[j])
print(last)
print(" ".join(map(str, arr[2:])))


import math

def eratosthenes(n):
	is_composite = [False for _ in range(n+1)]
	is_composite[0] = is_composite[1] = True

	b = math.floor(math.sqrt(n)) + 1

	for p in range(2, b+1):
		if is_composite[p]:
			continue

		x = 2*p
		while x <= n:
			is_composite[x] = True
			x += p

	return is_composite
	#return [k for k in range(2, n+1) if not is_composite[k]]

n = int(input())
is_composite = eratosthenes(n+1)

if n >= 3:
	print(2)
else:
	print(1)

print(*(1 if not is_composite[k] else 2 for k in range(2, n+2)))




n = int(input())

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

for i in range(2, n+2):
    if r[i] == 1:
        for j in range(i*i, n+2, i):
            r[j] = 2
if n < 3:
    print(1)
else:
    print(2)
print(*r[2:])


n=int(input())
ans=[1 for _ in range(n+2)]
for i in range(2,int(n**0.5)+2):
    if ans[i]==2: continue
    for j in range(i*2,n+2,i):
        ans[j]=2
print(len(set(ans)))
print(*ans[2:])

import sys

fin = sys.stdin
fout = sys.stdout
n = int(fin.readline())
colors = [1] * n
allCount = 1
for i in range(2, n + 2):
    if colors[i - 2] == 1 and i * i <= n + 1:
        allCount += 1
        for j in range(i * i, n + 2, i):
            colors[j - 2] = 2
fout.write(str(max(colors)) + '\n')
fout.write(' '.join(map(str, colors)))


import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

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

    if n <= 2:
        k = 1
        ans = [1]*n
        print(k)
        print(*ans)
    else:
        k = 2
        ans = color(n)
        print(k)
        print(*ans)

def color(n):
    res = [1] * (n + 2) # 0, 1, 2, 3, ..., n + 1
    for p in range(2, n + 2):
        if res[p] != 1:
            continue
        for q in range(p*p, n + 2, p):
            res[q] = 2

    # debug(res, locals())

    return res[2:]

def __starting_point():
    solve()
__starting_point()

from math import sqrt

def prime(a):
    if a < 2: return False
    for x in range(2, int(sqrt(a)) + 1):
        if a % x == 0:
            return False
    return True

prime_lst = []
n = int(input())

if n < 3:
    print(1)
else:
    print(2)
for i in range(2, n+2):
    if prime(i):
        print(1, end=" ")
    else:
        print(2, end=" ")


n = int(input())+2

prime = [i%2 for i in range(n)]
prime[1] = 0
prime[2] = 1
for p in range(3, int(n**0.5)+2, 2):
    if not prime[p]:
        continue
    for q in range(p*p, n, p+p):
        prime[q] = 0

l = [2-x for x in prime[2:]]
print(max(l))
print(" ".join(map(str, l)))


def primes_upto(limit):
    num_list = [1 for i in range(0, limit + 1)]
    ctr = 2
    is_prime = [True]*(limit+1)
    for n in range(2, int(limit**0.5) + 1): # stop at ``sqrt(limit)``
        if is_prime[n]:
            for i in range(n*n, limit + 1, n):
                is_prime[i] = False
                num_list[i] = ctr
    del num_list[0]
    del num_list[1]
    return num_list


def main():
    jewels = int(input())
    result = primes_upto(jewels + 1)
    print(len(set(result)))
    for i in result:
        print(i, end=' ')


def __starting_point():
    main()

__starting_point()

def dfs(v, col):
    used[v] = col
    for u in g[v]:
        if used[u] == -1:
            dfs(u, col ^ 1)

n = int(input())
used = [1 for i in range(n)]
for i in range(2, n + 2):
    if used[i - 2] == 1:
        for j in range(i * i, n + 2, i):
            used[j - 2] = 2
print(max(used))
print(*used)


import sys
n = int(input())
col = [1 for i in range(n+2)]
curprime = 1
ans = 0
if n <= 2:
    print(1)
    for i in range(n):
        print(1, end = ' ')
    return
while True:
    prime = curprime + 1;
    while  prime <= n + 1  and col[prime] == 2:
        prime += 1
    if prime >= n + 1:
        break;
    for i in range(prime + prime,n + 2,prime):
        col[i] = 2
    curprime = prime
print(2)
for i in range(2, n  + 2):
    print(col[i], end = ' ')

n = int(input())
prizes = [1 for i in range(n)]
for j in range(int(n**(1/2))):
    if prizes[j] == 1:
        for i in range(2*j+2, n, j+2):
            prizes[i] = 2
if n > 2:
    print(2)
else:
    print(1)
for num in prizes:
    print(num, end=' ')

n = int(input())
res = 1

piece = [1 for i in range(n+2)]
for i in range(2, n+2):
    if piece[i] != 1:
        continue
    for j in range(i+i, n+2, i):
        piece[j] = 2

for p in piece:
   res = max(p, res)
print(res)
print(" ".join(map(str, piece[2:])))


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

    if n == 1:
        print("1")
        print("1")
        return
    elif n == 2:
        print("1")
        print("1 1")
        return
    elif n == 3:
        print("2")
        print("1 1 2")
        return
    else:
        numbers = [True] * (n+3)
        for prime in range(2, n+3):
            for i in range(2 * prime, n+3, prime):
                numbers[i] = False

        print(2)
        print(" ".join([str(1) if numbers[i+2] else str(2) for i in range(n)]))


def __starting_point():
    main()

__starting_point()


def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

def main():
	n=int(input())
	if n==1:
		print('1\n1')
	elif n==2:
		print('1\n1 1')
		# //fkdjfk
	else:
		cnt=1
		ans=[]
		for i in range(1,n+1):
			if isprime(i+1):
				ans.append(1)
			else:
				ans.append(2)
				cnt=2
		print(cnt)
		for i in ans:
			print(i,end=' ')
		print('\n')

def __starting_point():
	main()


__starting_point()

def is_prime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

n = int(input())
ans = []
for i in range(2, n+2):
    if is_prime(i):
        ans.append(1)
    else:
        ans.append(2)
if n == 1:
    print(1)
    print(1)
elif n == 2:
    print(1)
    print(1, 1)
else:
    print(2)
    print(" ".join(str(num) for num in ans))


n = int(input())
prime = [True]*(n+2)
prime[0] = prime[1] = False
for m in range(2,n+2):
    if prime[m]:
        for i in range(2*m,n+2,m):
            prime[i] = False
print('2' if n>2 else '1')
colors = ['1' if prime[m] else '2' for m in range(2, n+2)]
print(' '.join(colors))