Problem: You're given an integer n. For every integer i from 2 to n, assign a positive integer a_i such that the following conditions hold:

  * For any pair of integers (i,j), if i and j are coprime, a_i ≠ a_j. 
  * The maximal value of all a_i should be minimized (that is, as small as possible). 



A pair of integers is called [coprime](https://en.wikipedia.org/wiki/Coprime_integers) if their [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) is 1.

Input

The only line contains the integer n (2 ≤ n ≤ 10^5).

Output

Print n-1 integers, a_2, a_3, …, a_n (1 ≤ a_i ≤ n). 

If there are multiple solutions, print any of them.

Examples

Input


4


Output


1 2 1 

Input


3


Output


2 1

Note

In the first example, notice that 3 and 4 are coprime, so a_3 ≠ a_4. Also, notice that a=[1,2,3] satisfies the first condition, but it's not a correct answer because its maximal value is 3.

Solution (in PYTHON3):

Solution:
import os, sys, shutil, glob, re
import time, calendar
from datetime import datetime, timezone
import hashlib, zipfile, zlib
from math import *
from operator import itemgetter
from functools import wraps, cmp_to_key, reduce, lru_cache
from itertools import count, combinations, permutations
from collections import namedtuple, defaultdict, Counter, deque
from queue import Queue
from bisect import bisect_left, bisect_right
class CustomException(Exception): pass

if os.getenv('SJDEAK'):
  # sys.stdin = open(os.path.expanduser('./in.txt'))
  # sys.stdout = open(os.path.expanduser('./out.txt'), 'w')
  debug = print
else:
  debug = lambda *args, **kwargs: None


def sieve(n):
  """返回[0, n]内的素数组成的迭代器"""
  isp = [1] * (n + 1)
  isp[0] = isp[1] = 0
  pCnt = 0
  for i in range(2, n + 1):
    if isp[i]:
      pCnt += 1
      for j in range(i * i, i * (n // i + 1), i):
        isp[j] = pCnt

if __name__ == '__main__':
  N = int(input())
  ans = []
  primeCnt = 0

  isp = [(True, 0)] * (N + 1)
  isp[0] = isp[1] = (False, 0)
  pCnt = 0
  for i in range(2, N + 1):
    if isp[i][0]:
      pCnt += 1
      isp[i] = (True, pCnt)
      for j in range(i * i, i * (N // i + 1), i):
        isp[j] = (False, pCnt)
      # print('isp:', isp)

  print(*map(itemgetter(1), isp[2:]))