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:
n = int(input())

numbers = list(range(2, n + 1))
arr = [0] * (n - 1)
counter = 0
for number in numbers:
    if number != 0:
        counter += 1
        arr[number - 2] = counter
        for candidate in range(2 * number, n+1, number):
            numbers[candidate-2] = 0
            arr[candidate - 2] = counter
# print(numbers)
print(*arr)

# primes = list(filter(lambda x: x != 0, numbers))
#
# for i in range(2, n + 1):
#     for j in range(len(primes)):
#         if not i % primes[j]:
#             print(j + 1, end=' ')
#             break




# def g(a, b):
#     while b:
#         a, b = b, a % b
#     return a + b
#
# for i in range(2, n + 1):
#     print(i, end=': ')
#     for j in range(2, n + 1):
#         if g(i, j) != 1:
#             print(j, end=' ')
#     print()