#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cmath>

#include <queue>

#include <deque>

#include <map>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

ll n,a[maxn];

ll dp[maxn];

ll lower_bound(ll *a,int x,int y,ll v){

    int m;

    while(x<y){

        m=x+(y-x)/;

        if(a[m]>=v)y=m;

        else x=m+;

    }

    return x;

}

ll q[maxn],r[maxn];

int main(){

    int o=;

    while(scanf("%lld",&n)!=EOF){

        for(int i=;i<n;i++){

            scanf("%lld%lld",&q[i],&r[i]);

        }

        for(int i=;i<n;i++){

            a[q[i]-]=r[i]-;

        }

        int m=;

        for(int i=;i<n;i++){

            if(m==||dp[m-]<a[i]){

                dp[m++]=a[i];

            }else{

                ll j=lower_bound(dp,,m,a[i]);

                dp[j]=a[i];

            }

            /*验证正确性

            for(int j=0;j<m;j++){

                printf("%lld ",dp[j]);

            }printf("\n");

            */

        }

        printf("Case %d:\n",o++);

        printf("My king, at most %d road",m);

        if(m>)printf("s");

        printf(" can be built.\n\n");

    }

    return ;

}