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.
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()
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()