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.math.*;
import java.util.*;
import java.io.*;
public class Main {
class Node implements Comparable<Node> {
   int id;
   int x;
   public Node(int id,int x){
      this.id=id;
      this.x=x;
   }
   public int compareTo(Node c){
      int t=Long.compare(this.x,c.x);
      if(t!=0) return t;
      t=Integer.compare(this.id,c.id);
      return t;
   }
}
   void solve(){
    n=ni();

      a=new int[n+1];
      int num=1;

      for(int i=2;i<=n;i++){
         if(a[i]==0){
            for(int j=i;j<=n;j+=i){
               a[j]=num;
            }
            num++;
         }
      }
      for(int i=2;i<=n;i++) pw.print(a[i]+" ");
      pw.println("");


   }
   int a[];
   int n;
   boolean check(){
      int r=a[1]%2;
      for(int i=1;i<=n;i++) if(a[i]%2!=r) return false;
      return true;
   }

   long add(long a,long b){
      a+=b;
      if(a>=M) a-=M;
      return a;
   }
   long mul(long a,long b){
      a*=b;
      if(a>=M) a%=M;
      return a;
   }
   long sub(long a,long b){
      a-=b;
      if(a<0) a+=M;
      return a;
   }
 long modpow(long x, long y, long M){

      long res = 1;

      x = x % M;

      while (y > 0)
      {

         if((y & 1)==1)
            res = (res * x) % M;

         y = y >> 1;
         x = (x * x) % M;
      }
      return res;
   }
   long modInverse(long A,long M){
      return modpow(A,M-2,M);
   }


   long M =(long)1e9+7;


   InputStream is;
   PrintWriter pw;
   String INPUT = "";

   void run() throws Exception {
      is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
      pw = new PrintWriter(System.out);
      long s = System.currentTimeMillis();
      solve();
      pw.flush();
      if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");


   }

   public static void main(String[] args) throws Exception {
      new Main().run();
   }

   private byte[] inbuf = new byte[1024];
   public int lenbuf = 0, ptrbuf = 0;

   private int readByte() {
      if (lenbuf == -1) throw new InputMismatchException();
      if (ptrbuf >= lenbuf) {
         ptrbuf = 0;
         try {
            lenbuf = is.read(inbuf);
         } catch (IOException e) {
            throw new InputMismatchException();
         }
         if (lenbuf <= 0) return -1;
      }
      return inbuf[ptrbuf++];
   }

   private boolean isSpaceChar(int c) {
      return !(c >= 33 && c <= 126);
   }

   private int skip() {
      int b;
      while ((b = readByte()) != -1 && isSpaceChar(b)) ;
      return b;
   }

   private double nd() {
      return Double.parseDouble(ns());
   }

   private char nc() {
      return (char) skip();
   }

   private String ns() {
      int b = skip();
      StringBuilder sb = new StringBuilder();
      while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
         sb.appendCodePoint(b);
         b = readByte();
      }
      return sb.toString();
   }

   private char[] ns(int n) {
      char[] buf = new char[n];
      int b = skip(), p = 0;
      while (p < n && !(isSpaceChar(b))) {
         buf[p++] = (char) b;
         b = readByte();
      }
      return n == p ? buf : Arrays.copyOf(buf, p);
   }

   private char[][] nm(int n, int m) {
      char[][] map = new char[n][];
      for (int i = 0; i < n; i++) map[i] = ns(m);
      return map;
   }

   private int[] na(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++) a[i] = ni();
      return a;
   }

   private int ni() {
      int num = 0, b;
      boolean minus = false;
      while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
      if (b == '-') {
         minus = true;
         b = readByte();
      }

      while (true) {
         if (b >= '0' && b <= '9') {
            num = num * 10 + (b - '0');
         } else {
            return minus ? -num : num;
         }
         b = readByte();
      }
   }

   private long nl() {
      long num = 0;
      int b;
      boolean minus = false;
      while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
      if (b == '-') {
         minus = true;
         b = readByte();
      }

      while (true) {
         if (b >= '0' && b <= '9') {
            num = num * 10 + (b - '0');
         } else {
            return minus ? -num : num;
         }
         b = readByte();
      }
   }

   private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

   private void tr(Object... o) {
      if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
   }

}