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:
/*           
                      
                     _.!._
                    /O*@*O\
                   <\@(_)@/>
          ,;,   .--;`     `;--.   ,
          O@O_ /   |d     b|   \ _hnn
          | `/ \   |       |   / \` |
          &&&&  :##;\     /;##;  &&&&
          |  \ / `##/|   |##'  \ /  |
          \   %%%%`</|   |#'`%%%%   /
           '._|_ \   |   |'  / _|_.'
             _/  /   \   \   \  \
            / (\(     '.  '-._&&&&
           (  ()##,    o'--.._`\-)
            '-():`##########'()()()
             /:::::/()`Y`()\:::::\
             \::::( () | () )::::/
              `"""`\().'.()/'"""`


                                                
                              +''''`--''-..`--..__
                             .\ _,/:i--._`:-:+._`.``-._
                            /`.._,,' \   `-.``--:.b....=.
                           |`..__,,..`.    '`.__::i--.-::_
                           )- .....--i'\..      --+`'''-'
                         ,' .'.._,.-'|._-b\
                        /,'<'    0   `i| \\             
                       |/ -|,--.." ,'-. ||\\\      |||||||||
                       ''/ |  O ' |  O '\ \\\\   _/        _\
                      |,','|    , .     | \\\\\\||  |||||  ||
                   ._,:'/ /-\   '^'   -Y"\\     ||  |||||  ||
                  .|/,'| |/':: ':=:' ,'|  |     ||  |||||  ||
                  |+,';' /|_/ \     _/ \b':.\  \'|       ,'
                  ,,:-i''_i' | ``-.Y',. ,|`: | \;- | |_,'
            __   |'| |i:'._ ,'     ,' ,; | |-)-'  __--:b__
           .P|   | |/,'|\  - ._   /  /   _,Y-   ,:/'  `.  `'".._
          ,'|| -','' | ._i._   `':| ,..,'     ,Y;'      \       `- ._
         |||||,..    | \ '-.._ _,' /       _,b-'         `.         '-.
         ||||P..i,  .| '....,-' _,'''''-'''               '    _,..    `\
         +'`   <'/  |`-.....---'                       ._         ,._
          |      |                                    ,'``,:-''''/,--`.
         Y|.b_,,:  |              ||                 ,;,Y'      /     |.
       ,' /'----' .'|   ..       |  |         '"   .`Y'     .,-b_....;;,.
      |+|,'     | | \.,  '      ,'  `:.  _     ,/__`     _=:  _,'``-
     / +,'      | /\_........:.'      '"----:::::'Y  .'.|   |||
     |' '      .'/- \\                          /'|| || |   |||
     |||      /|     \L                        /'|| ||/ |   |||
     `.|    ,'/       .|                      / ,'||/o;/    |||
       `..._,,         |                      |/|   '       |||
         ``-'          |                      |,            |||
                       |          ,.          |             |||
    ,=--------....     |          ""          |             |||
  ,/,'.            i=..+._             ,..    '..;---:::''- | |
  '/|           __....b `-''`---....../.,Y'''''j:.,.._      | `._
  .'      _.Y.-'       `..       ii:,'--------' |     :-+. .| | b\
  |     .=_,.---'''''--...:..--:'  /         _..-----..:=   | | '|\
  |    '-''`'---                  ---'_,,,--''           `,.. |  | \.
   \  .                      ,' _,--''        ::      _,/ |||   |  \
  `::b\`                 _,-i,-'                 ,..---'    ,|:|  | _|
  `'--.:-._      ____,,,;.,'' `--._      ''''''''           |'|' .'  '
       ``'--....Y''-'              `''--..._..____._____...,' |  'o-'
                                               `''''`'''i==_+=_=i__
                                                       ||'''- '    `.
                                                        `-.......-''  
*/


//package cf;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
import java.io.*;
import java.lang.*;
public class Three{
    public static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
     
        public int read() {
            if (numChars==-1)
                throw new InputMismatchException();
     
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
     
                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
     
            while(isSpaceChar(c))
                c = read();
     
            int sgn = 1;
     
            if (c == '-') {
                sgn = -1;
                c = read();
            }
     
            int res = 0;
            do {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
     
            return res * sgn;
        }
     
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
     
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }
     
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
     
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));
     
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
     
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
 
    static long gcd(long a, long b){
        if (a == 0)
            return b;  
        return gcd(b % a, a);  
    }
    static long lcm(long a, long b)  {
        return (a*b)/gcd(a, b);  
    }
    
    // Select a particular column and the entire rows will be shifted and the selected column will be sorted while other columns will be 
    // rearranged accordingly
    public static void sortbyColumn(int arr[][], int col) 
    { 
        
        Arrays.sort(arr, new Comparator<int[]>() { 
            
          @Override              
          
          public int compare(final int[] entry1,  
                             final int[] entry2) { 
  
            
            if (entry1[col] > entry2[col]) 
                return 1; 
            else
                return -1; 
          } 
        });  
    } 
    
    // Max contigious subArray sum
    static long func(long a[],int size,int s){
        long max1=a[s];
        long maxc=a[s];
        for(int i=s+1;i<size;i++){
            maxc=Math.max(a[i],maxc+a[i]);
            max1=Math.max(maxc,max1);
        }
        return max1;
    }
    // public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
    //     public U x;
    //     public V y;
    
    //     public Pair(U x, V y) {
    //         this.x = x;
    //         this.y = y;
    //     }
    
    //     public int hashCode() {
    //         return (x == null ? 0 : x.hashCode() * 31) + (y == null ? 0 : y.hashCode());
    //     }
    
    //     public boolean equals(Object o) {
    //         if (this == o)
    //             return true;
    //         if (o == null || getClass() != o.getClass())
    //             return false;
    //         Pair<U, V> p = (Pair<U, V>) o;
    //         return (x == null ? p.x == null : x.equals(p.x)) && (y == null ? p.y == null : y.equals(p.y));
    //     }
    
    //     public int compareTo(Pair<U, V> b) {
    //         int cmpU = x.compareTo(b.x);
    //         return cmpU != 0 ? cmpU : y.compareTo(b.y);
    //     }
    
    //     public String toString() {
    //         return String.format("(%s, %s)", x.toString(), y.toString());
    //     }
    
    // }
    // static class MultiSet<U extends Comparable<U>> {
    //     public int sz = 0;
    //     public TreeMap<U, Integer> t;
 
    //     public MultiSet() {
    //         t = new TreeMap<>();
    //     }
 
    //     public void add(U x) {
    //         t.put(x, t.getOrDefault(x, 0) + 1);
    //         sz++;
    //     }
 
    //     public void remove(U x) {
    //         if (t.get(x) == 1) t.remove(x);
    //         else t.put(x, t.get(x) - 1);
    //         sz--;
    //     }
 
    // }
    static long myceil(long a, long b){
        return (a+b-1)/b;
    }
    
    // Combination 
    static long C(long n,long r){
        long count=0,temp=n;
        long ans=1;
        long num=n-r+1,div=1;
        while(num<=n){
            ans*=num;
            //ans+=MOD;
            ans%=MOD;
            ans*=mypow(div,MOD-2);
            //ans+=MOD;
            ans%=MOD;
            num++;
            div++;
        }
        
        ans+=MOD;
        return ans%MOD;
    }
    
    static void sieve(int n){
    	// Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
 
        for (int p = 2; p * p <= n; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true)
            {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
 
        // Print all prime numbers
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
                li.add(i);
        }
    }
    
    static void primeFactorSieve(int n){
        is_sieve[0]=1;
        is_sieve[1]=1;
        int i,j,k;
        for(i=2;i<n;i++){
            if(is_sieve[i]==0){
                sieve[i]=i;
                li.add(i);
                for(j=i*i;j<n;j+=i){
                    if(j>n||j<0){
                        break;
                    }
                    is_sieve[j]=1;
                    sieve[j]=i;
                }
            }
        }
    }
    
    static long mypow(long x,long y){
        long temp; 
        if( y == 0) 
            return 1; 
        temp = mypow(x, y/2); 
        if (y%2 == 0) 
            return (temp*temp)%MOD; 
        else
            return ((x*temp)%MOD*(temp)%MOD)%MOD; 
    }
    static long dist[],dp[][];
    static int visited[],isit[];
    static ArrayList<Integer> adj[],li;
    //static int dp[][][];
    static int MOD=1000000007,max=0;
    static char ch[];
    static int[] sieve,is_sieve;
    static TreeSet<Integer> tr;
    
    static int calcdist(int r1,int c1,int r2,int c2){
        if(r2-r1==c2-c1){
            return isRight(r1,c1)?0:r2-r1;
        }
        
        r2-=r1-1;
        c2-=c1-1;
        if(isLeft(r1,c1)){
            return (r2-c2)/2;
        }else{
            return (r2-c2+1)/2;
        }
    }
    
    static boolean isLeft(int r,int c){
        if((r+c)%2==0){
            return true;
        }
        return false;
    }
    
    static boolean isRight(int r,int c){
        if((r+c)%2!=0){
            return true;
        }
        return false;
    }
    static int binarySearch(List<Long> ll , long x) 
	{ 
		int l = 0, r = ll.size() - 1; 
		while (l <= r) { 
			int m = l + (r - l) / 2; 

			// Check if x is present at mid 
			if (ll.get(m) == x) 
				return m; 

			// If x greater, ignore left half 
			if (ll.get(m) < x) 
				l = m + 1; 

			// If x is smaller, ignore right half 
			else
				r = m - 1; 
		} 

		// if we reach here, then element was 
		// not present 
		return l-1; 
	} 

    public static void sieve1(int n)
    {
        boolean isprime[] = new boolean[n+1];

        Arrays.fill(isprime,true);
        for(int i = 2;i*i<=n;i++)
        {
            if(isprime[i])
            {
                for(int j = i*i;j<=n;j+=i)
                    isprime[j] = false;
            }
        }
        for(int i = 1;i<=n;i++)
            if(isprime[i])
                li.add(i);
    }
    

    public static void main(String args[]){
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader sc = new InputReader(inputStream);
        PrintWriter w = new PrintWriter(outputStream);
        
        int n = sc.nextInt();
        li = new ArrayList<>();
        sieve1(n);
        // for(int i : li)
        //     System.out.println(i);
        for(int i = 2;i<=n;i++)
        {
            int j = 1;
           // boolean flag = false;
            while(j<li.size() && li.get(j) <= i)
            {
                if(i%li.get(j) == 0)
                {
                    w.print((j)+" ");
                    //flag = true;
                    break;
                }

                j++;
            }
        }
        w.close(); 
    }
}