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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "\ndef isprime(n):\n    '''check if integer n is a prime'''\n    # make sure n is a positive integer\n    n = abs(int(n))\n    # 0 and 1 are not primes\n    if n < 2:\n        return False\n    # 2 is the only even prime number\n    if n == 2: \n        return True    \n    # all other even numbers are not primes\n    if not n & 1: \n        return False\n    # range starts with 3 and only needs to go up the squareroot of n\n    # for all odd numbers\n    for x in range(3, int(n**0.5)+1, 2):\n        if n % x == 0:\n            return False\n    return True\n\ndef main():\n\tn=int(input())\n\tif n==1:\n\t\tprint('1\\n1')\n\telif n==2:\n\t\tprint('1\\n1 1')\n\t\t# //fkdjfk\n\telse:\n\t\tcnt=1\n\t\tans=[]\n\t\tfor i in range(1,n+1):\n\t\t\tif isprime(i+1):\n\t\t\t\tans.append(1)\n\t\t\telse:\n\t\t\t\tans.append(2)\n\t\t\t\tcnt=2\n\t\tprint(cnt)\n\t\tfor i in ans:\n\t\t\tprint(i,end=' ')\n\t\tprint('\\n')\n\ndef __starting_point():\n\tmain()\n\n\n__starting_point()"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14013