#include<bits/stdc++.h>
using namespace std;
int x;
int primes[100005],cnt;
bool st[100005];
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
int main()
{
    scanf("%d",&x);
    init(x+4);
    if(x==2||x==1) printf("1\n");
    else printf("2\n");
    for(int i=2;i<=x+1;i++)
        if(st[i]) printf("2 ");
        else printf("1 ");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int x;
int primes[1000010],cnt;
bool st[1000010];
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
int main()
{
    init(1000009);
    while(scanf("%d",&x))
    {
        if(!x) break;
        for(int i=1;;i++)
        {
            int a=primes[i];
            int b=x-a;
            if(!st[b])
            {
                printf("%d = %d + %d\n",x,a,b);
                break;
            }
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=20;
const ll mod=(ll)(1e9+7);
ll bit[maxn],tp[maxn];
struct node
{
    ll cnt;  
    ll sum;    
    ll sqsum; 
    node(ll _cnt=0,ll _sum=0,ll _sqsum=0):cnt(_cnt),sum(_sum),sqsum(_sqsum){}
}F[maxn][maxn][maxn];
node dfs(int pos,int sum,int ori,bool lead,bool limit)
{   
    node ret, tmp;
    if(!pos) return node((sum&&ori), 0, 0);
    if(!limit && !lead && F[pos][sum][ori].cnt != -1) return F[pos][sum][ori];
    int endi=limit?bit[pos]:9;
    tmp=node(0, 0, 0);
    for (int i = 0; i <= endi; i ++) {
        if(i == 7) continue;
        ret = dfs(pos-1, (sum+i)%7, (ori*10+i)%7, lead&&!i, limit&&(i==endi));
        tmp.cnt = (tmp.cnt + ret.cnt) % mod;
        tmp.sum = (tmp.sum + ret.sum + ret.cnt * i % mod * tp[pos-1] % mod) % mod;
        tmp.sqsum = (tmp.sqsum + ret.sqsum + 2 * ret.sum % mod * i % mod * tp[pos-1] % mod) % mod;
        tmp.sqsum = (tmp.sqsum + i * i * tp[pos-1] % mod * tp[pos-1] % mod * ret.cnt % mod) % mod;
    }
    return (!limit&&!lead) ? F[pos][sum][ori] = tmp: tmp;
}
ll solve(ll x)
{
    bit[0]=0;
    while(x){
        bit[++bit[0]]=x%10;
        x/=10;
    }
    return dfs(bit[0],0,0,1,1).sqsum;
}
int main()
{
    memset(F,-1,sizeof(F));
    tp[0] = 1;
    for (int i=1; i<=19; ++i) tp[i]=tp[i-1]*10 % mod;
    int T;
    scanf("%d", &T);
    while (T--) {
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", (solve(R) - solve(L-1) + mod) % mod);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
const int N = 500010;
int n,ww;
int w[1005],v[1005],dp[1005];
ll cnt[1005];
int main()
{
    scanf("%d%d",&n,&ww);
    for(int i=0;i<=ww;i++) cnt[i]=1;
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
    for(int i=1;i<=n;i++)
        for(int j=ww;j>=w[i];j--)
        {
            if(dp[j]<dp[j-w[i]]+v[i])
                cnt[j]=cnt[j-w[i]];
            else if(dp[j]==dp[j-w[i]]+v[i])
            {
                cnt[j]+=cnt[j-w[i]];
                cnt[j]%=mod;
            }
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    printf("%lld",cnt[ww]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
const int N = 500010;
int n;
ll q[N], w[N];
ll merge_sort(int l, int r)
{
    if (l == r) return 0;
    int mid = l + r >> 1;
    ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            w[k ++ ] = q[j ++ ];
        }
    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];
    return res;
}
int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        printf("%lld\n", merge_sort(0, n - 1));
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        priority_queue<int, vector<int>, greater<int>> sml;
        priority_queue<int> big;
        int idx, n, mid,cnt=1;
        scanf("%d%d%d",&idx, &n, &mid);
        printf("%d %d\n%d ", idx,(n+1)/2,mid);
        for (int i = 2, x; i <= n; i++)
        {
            scanf("%d", &x);
            if (x > mid) sml.push(x);
            else big.push(x);
            if (i & 1)
            {
                while (sml.size() != big.size())
                    if (big.size() > sml.size())
                    {
                        sml.push(mid);
                        mid = big.top();
                        big.pop();
                    }
                    else
                    {
                        big.push(mid);
                        mid = sml.top();
                        sml.pop();
                    }
                cnt++;
                if(cnt==11) {printf("\n");cnt=1;}
                printf("%d ", mid);
            }
        }
        printf("\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int l,r,n,a[35];
int dp[35][320];
int dfs(int pos,int sum,bool limit)
{
    if(!pos) return sum%n==0;
    if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
    int ans=0,end=limit?a[pos]:9;
    for(int i=0;i<=end;i++)
        ans+=dfs(pos-1,sum+i,limit&&i==end);
    if(!limit) dp[pos][sum]=ans;
    return ans;
}
int solve(int x)
{
    memset(dp,-1,sizeof(dp));
    int pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,1);
}
int main()
{
    while(scanf("%d%d%d",&l,&r,&n)!=EOF)
        printf("%d\n",solve(r)-solve(l-1));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int a[20];
ll dp[20][20];
int dfs(int pos,bool lead0,int pre,bool limit)
{
    if(!pos) return 1;
    if(lead0&&!limit&&dp[pos][pre]!=-1) return dp[pos][pre];
    int ans=0,end=limit?a[pos]:9;
    for(int i=0;i<=end;i++)
    {
        if(lead0&&abs(pre-i)<2) continue;
        ans+=dfs(pos-1,lead0||i,i,limit&&i==end);
    }
    if(lead0&&!limit) dp[pos][pre]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,1);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d",solve(r)-solve(l-1));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int l,r,a[35];
int dp[35][11];
int dfs(int pos,int pre,bool limit)
{
    if(!pos) return 1;
    if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];
    int ans=0,end=limit?a[pos]:9;
    for(int i=0;i<=end;i++)
        if(i<pre) continue;
        else ans+=dfs(pos-1,i,limit&&i==end);
    if(!limit) dp[pos][pre]=ans;
    return ans;
}
int solve(int x)
{
    memset(dp,-1,sizeof(dp));
    int pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,1);
}
int main()
{
    while(scanf("%d%d",&l,&r)!=EOF)
        printf("%d\n",solve(r)-solve(l-1));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int l,r,k,b,a[35];
int dp[35][35];
int dfs(int pos,int cnt,bool limit)
{
    if(!pos) return cnt==k;
    if(!limit&&dp[pos][cnt]!=-1) return dp[pos][cnt];
    int ans=0,end=limit?min(a[pos],1):1;
    for(int i=0;i<=end;i++)
        if(cnt+i>k) continue;
        else ans+=dfs(pos-1,cnt+i,limit&&i==a[pos]);
    if(!limit) dp[pos][cnt]=ans;
    return ans;
}
int solve(int x)
{
    memset(dp,-1,sizeof(dp));
    int pos=0;
    while(x)
    {
        a[++pos]=x%b;
        x/=b;
    }
    return dfs(pos,0,1);
}
int main()
{
    scanf("%d%d%d%d",&l,&r,&k,&b);
    printf("%d",solve(r)-solve(l-1));
    return 0;
}

/*
763 8698
7
3
*/