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 JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
public class Main extends Thread  {
    boolean[] prime;
    FastScanner sc;
    PrintWriter pw;
    MathF mf;
    long startTime = System.currentTimeMillis();
    final class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        public long nlo() {
            return Long.parseLong(next());
        }

        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(next());
        }

        public String nli() {
            String line = "";
            if (st.hasMoreTokens()) line = st.nextToken();
            else try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            while (st.hasMoreTokens()) line += " " + st.nextToken();
            return line;
        }

        public double nd() {
            return Double.parseDouble(next());
        }
    }
    final class MathF {
        long[][] mul(long[][] arr,long[][] brr,int a,int b,int c,int d)
        {
            long[][] crr=new long[a][d];
            for(int i=0;i<a;i++)
            {
                for(int j=0;j<d;j++)
                {
                    for(int k=0;k<b;k++)
                    {
                        crr[i][j]+=(((arr[i][k]%1000000007)*(brr[k][j]%1000000007))%1000000007);
                    }
                }
            }
            return crr;
        }
        int sod(long a)
        {
            int ans=0;
            while(a!=0)
            {
                ans+=(a%10);
                a=a/10;
            }
            return ans;
        }
        long pow(long a,long b)
        {
            if(b==0)
                return 1;
            else
            {
                long x=pow(a,b/2);
                if(b%2==1)
                    return (x*x*a);
                else
                    return (x*x);
            }
        }
        public  long gcd(long a, long b) {
            return (b == 0 ? a : gcd(b, a % b));
        }
        public long exponent(long a,long b)
        {
            if(b==0)
                return 1;
            else
            {
                long x=exponent(a,b/2);
                x*=x;
                if(b%2==1)
                    x*=a;
                return x;
            }
        }
        public  int nod(long x) {
            int i = 0;
            while (x != 0) {
                i++;
                x = x / 10;
            }
            return i;
        }

        public  int nob(long x) {
            if(x==0)
                return 1;
            return (int) Math.floor(Math.log(x) / Math.log(2)) + 1;
        }

        public int[] FastradixSort(int[] f) {
            int[] to = new int[f.length];
            {
                int[] b = new int[65537];
                for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            {
                int[] b = new int[65537];
                for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            return f;
        }

        public  void Primesieve(int n) {
            prime=new boolean[n];
            for (int i = 0; i < n; i++)
                prime[i] = true;
            for (int p = 2; p * p < n; p++) {
                if (prime[p] == true) {
                    for (int i = p * p; i < n; i += p)
                        prime[i] = false;
                }
            }
        }
    }
    public Main(ThreadGroup t,Runnable r,String s,long d )
    {
        super(t,r,s,d);
    }
    public void run()
    {
        sc=new FastScanner();
        pw=new PrintWriter(System.out);
        mf=new MathF();
        solve();
        pw.flush();
        pw.close();
    }
    public static void main(String[] args)
    {
        new Main(null,null,"",1<<30).start();
    }


    /////////////------------------------------------//////////////
    ////////////------------------Main-Logic--------//////////////
    ///////////-------------------------------------//////////////


    public void solve() {
        int t = 1;
        while(t>0)
        {
            int n=sc.ni();
            int[] arr=new int[n+1];
            Arrays.fill(arr,0);
            int k=1,l;
            for(int i=2;i<=n;i++)
            {
                if(arr[i]==0)
                {
                    for(int j=i;j<=n;j+=i)
                    {
                        arr[j]=k;
                    }
                    k++;
                }
            }
            for(int i=2;i<=n;i++)
                pw.print(arr[i]+" ");
            t--;
        }
    }
}