stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <algorithm>

#include <climits>

#include <cmath>

#include <csignal>

#include <cstdio>

#include <cstdlib>

#include <functional>

#include <iomanip>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <string>

#include <tuple>

#include <vector>



using Graph = std::vector<std::vector<int>>;

using WGraph = std::vector<std::vector<std::pair<int, long long>>>;

using ll = long long;

using namespace std;



constexpr ll mod = 1000000007;

 

int main() {

    int n = 0;

    cin >> n;

    vector<int> a(n);

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

        cin >> a.at(i);

    }

    

    int cnt0 = 0;

    for (int x : a) {

        if (x == 0) {

            cnt0++;

        }

    }

 

    if (cnt0 > 3) {

        cout << 0 << endl;

        return 0;

    }

 

    ll color = (cnt0 == 1) ? 3 : 6;

 

    ll ans = 1;

    vector<ll> cur(1e5, 0);

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

        if (a.at(i) == 0) {

            cur.at(0)++;

        } else {

            ans *= cur.at(a.at(i)-1);

            ans %= mod;

            cur.at(a.at(i))++;

            cur.at(a.at(i)-1)--;

        }

    }

    

    cout << ans * color % mod << endl;

 

    return 0;

}


// Optimized solution to the same problem (faster):
#include <algorithm>

#include <climits>

#include <cmath>

#include <csignal>

#include <cstdio>

#include <cstdlib>

#include <functional>

#include <iomanip>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <string>

#include <tuple>

#include <vector>



using Graph = std::vector<std::vector<int>>;

using WGraph = std::vector<std::vector<std::pair<int, long long>>>;

using ll = long long;

using namespace std;



constexpr ll mod = 1000000007;

 

int main() {

    int n = 0;

    cin >> n;

    vector<int> a(n);

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

        cin >> a.at(i);

    }

    

    int cnt0 = 0;

    for (int x : a) {

        if (x == 0) {

            cnt0++;

        }

    }

 

    if (cnt0 > 3) {

        cout << 0 << endl;

        return 0;

    }

 

    ll color = (cnt0 == 1) ? 3 : 6;

 

    ll ans = 1;

    vector<int> cur(1e5, 0);

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

        if (a.at(i) == 0) {

            cur.at(0)++;

        } else {

            ans *= cur.at(a.at(i)-1);

            ans %= mod;

            cur.at(a.at(i))++;

            cur.at(a.at(i)-1)--;

        }

    }

    

    cout << ans * color % mod << endl;

 

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int MX = 1e5+3, MOD = 1e9+7;

int a[MX];

vector<int> pos[MX];

long long ans = 1;

int main() {

	ios::sync_with_stdio(0);cin.tie(0);

	int n, mxp = 0;

	cin >> n;

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

		cin >> a[i];

		pos[a[i]].push_back(i);

		mxp = max(mxp, a[i]);

		if(pos[a[i]].size() > 3)

			return !(cout << 0);

	}

	for(int i=0; i<=mxp; i++) {

		if(pos[i].empty() || (i && pos[i-1].size() < pos[i].size()))

			return !(cout << 0);

	}

	ans = (pos[0].size() >= 2 ? 6 : 3);

	for(int i=1; i<=mxp; i++) {

		int p = 0;

		for(int t: pos[i]) {

			int cnt = 0;

			for(int s: pos[i-1]) {

				cnt += s < t;

			}

			if(cnt <= p)

				return !(cout << 0);

			ans *= (cnt - p);

			p++;

		}

		ans %= MOD;

	}

	cout << ans;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main() {

	ios::sync_with_stdio(0);cin.tie(0);

	int n;

	cin >> n;

	int t[3] = {0,0,0};

	long long ans = 1;

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

		int a;

		cin >> a;

		int p = -1, cnt = 0;

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

			if(t[j] == a) {

				p = j;

				cnt++;

			}

		}

		ans *= cnt;

		t[p]++;

		ans %= (int)(1e9+7);

	}

	cout << ans;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <vector>

#include <map>

#include <queue> 

#include <stack>

#include <set>

#include <list>



using namespace std;

typedef long long ll;

#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))

#define all(x) x.begin(),x.end()





int main()

{

	int n; cin >> n;

	ll ans = 1;

	vector<int> num(100100, 0);

	num[0] = 3;

	rep(i, 0, n - 1)

	{

		int a; cin >> a;

		ans *= num[a];

		ans %= 1000000007;

		--num[a];

		++num[a + 1];

	}

	cout << ans << endl;

}


// Optimized solution to the same problem (faster):
#pragma region

#include <iostream>

#include <string>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <vector>

#include <map>

#include <queue> 

#include <stack>

#include <set>

#include <list>



using namespace std;

typedef long long ll;

//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))

#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))

#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))

#define all(x) x.begin(),x.end()

#pragma endregion





int main()

{

	int n; cin >> n;

	vector<ll> memo(3, 0);

	ll MOD = 1e9 + 7;

	ll res = 1;

	rep(i, n)

	{

		int a; cin >> a;

		ll cnt = 0;

		rep(i, 3)

		{

			if (memo[i] == a)++cnt;

		}

		res *= cnt;

		res %= MOD;

		rep(i, 3)

		{

			if (memo[i] == a)

			{

				++memo[i];

				break;

			}

		}

	}

	cout << res << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

const int MAX = 100000, mod = 1e9+7;

int A[MAX];

int main(){

    int n, maxi = 0;

    long long sum = 1;

    cin >> n;

    A[0] = 3;

    

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

    {

        int a;

        cin >> a;

        sum = (sum * A[a]) % mod;

        A[a]--;

        A[a+1]++;

    }

    cout << sum << endl;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

using namespace std;

const int MAX = 100000, mod = 1e9+7;

int A[MAX];

int main(){

    int n;

    long long sum = 1;

    scanf("%d", &n);

    A[0] = 3;

    

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

    {

        int a;

        scanf("%d", &a);

        sum = (sum * A[a]) % mod;

        A[a]--;

        A[a+1]++;

    }

    printf("%ld", sum);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// E



#include <bits/stdc++.h>

using ll = long long;

using namespace std;

ll mod=1e9+7;



int main(){

  int N,A[100000];

  cin>>N;

  for (int i(0);i<N;i++) cin>>A[i];

  ll dp[100001][3] = {0};



  for (int i(1);i<=N;i++){

    bool flag = true;

    for (int j(0);j<3;j++){

      if (dp[i-1][j] == A[i-1] && flag == true){

        dp[i][j] = dp[i-1][j]+1;

        flag = false;

      } else {

        dp[i][j] = dp[i-1][j];

      }

    }

    sort(dp[i],dp[i]+3,greater<int>());

  }



  ll cnt(1);

  for (int i(0);i<N;i++){

    int cnti(0);

    for (int j(0);j<3;j++){

      if (A[i] == dp[i][j]) cnti++;

    }

    cnt*= cnti;

    cnt%=mod;

  }

  cout << cnt << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
// E



#include <bits/stdc++.h>

using ll = long long;

using namespace std;

ll mod=1e9+7;



int main(){

  int N,A[100000];

  cin>>N;

  for (int i(0);i<N;i++) cin>>A[i];

  int dp[100001][3] = {0};



  for (int i(1);i<=N;i++){

    bool flag = true;

    for (int j(0);j<3;j++){

      if (dp[i-1][j] == A[i-1] && flag == true){

        dp[i][j] = dp[i-1][j]+1;

        flag = false;

      } else {

        dp[i][j] = dp[i-1][j];

      }

    }

    sort(dp[i],dp[i]+3,greater<int>());

  }



  ll cnt(1);

  for (int i(0);i<N;i++){

    int cnti(0);

    for (int j(0);j<3;j++){

      if (A[i] == dp[i][j]) cnti++;

    }

    cnt*= cnti;

    cnt%=mod;

  }

  cout << cnt << endl;

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<queue>

#include<iostream>

#include<string>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

int main(){

  int i,j;

  int a[1002][1002],c[10],d[10],n,w,h,x,y,z;

  int sm=0;

  char s;

  bool b[1002][1002];

  queue<pair<pair<int,int>,int> > q;

  memset(a,-1,sizeof(a));

  cin>>h>>w>>n;

  for(i=1;i<h+1;i++){

    for(j=1;j<w+1;j++){

      cin>>s;

      if(s!='X'){

	a[j][i]=0;

	if(0){

	}else if(s=='.'){

	}else if(s=='S'){

	  c[0]=j;

	  d[0]=i;

	}else{

	  c[s-'0']=j;

	  d[s-'0']=i;

	}

      }

    }

  }

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

    memset(b,0,sizeof(b));

    while(q.empty()==0)

      q.pop();

    q.push(make_pair(make_pair(c[i],d[i]),0));

    for(;;){

      x=q.front().first.first;

      y=q.front().first.second;

      z=q.front().second;

      q.pop();

      if(a[x][y]!=-1&&b[x][y]==0){

	if(x==c[i+1]&&y==d[i+1])

	  break;

	b[x][y]=1;

	q.push(make_pair(make_pair(x-1,y),z+1));

	q.push(make_pair(make_pair(x,y-1),z+1));

	q.push(make_pair(make_pair(x+1,y),z+1));

	q.push(make_pair(make_pair(x,y+1),z+1));

      }

    }

    sm+=z;

  }

  cout<<sm<<endl;

  return 0;

}

// Optimized solution to the same problem (faster):
#include<queue>

#include<iostream>

#include<string>

#include<cstdlib>

#include<cstring>

#include<cmath>

using namespace std;

int main(){

  int i,j;

  int c[10],d[10],n,w,h,x,y,z;

  int sm=0;

  char s;

  bool a[1002][1002],b[1002][1002];

  queue<pair<pair<int,int>,int> > q;

  memset(a,0,sizeof(a));

  cin>>h>>w>>n;

  for(i=1;i<h+1;i++){

    for(j=1;j<w+1;j++){

      cin>>s;

      if(s!='X'){

	a[j][i]=1;

	if(0){

	}else if(s=='.'){

	}else if(s=='S'){

	  c[0]=j;

	  d[0]=i;

	}else{

	  c[s-'0']=j;

	  d[s-'0']=i;

	}

      }

    }

  }

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

    memset(b,0,sizeof(b));

    while(q.empty()==0)

      q.pop();

    q.push(make_pair(make_pair(c[i],d[i]),0));

    for(;;){

      x=q.front().first.first;

      y=q.front().first.second;

      z=q.front().second;

      q.pop();

      if(a[x][y]&&b[x][y]==0){

	if(x==c[i+1]&&y==d[i+1])

	  break;

	b[x][y]=1;

	q.push(make_pair(make_pair(x-1,y),z+1));

	q.push(make_pair(make_pair(x,y-1),z+1));

	q.push(make_pair(make_pair(x+1,y),z+1));

	q.push(make_pair(make_pair(x,y+1),z+1));

      }

    }

    sm+=z;

  }

  cout<<sm<<endl;

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<deque>

#include<memory.h>



using namespace std;



int H, W, N;

char mapT[1000][1000];

int vis[1000][1000];

int temp_x = 0, temp_y;

char temp;

int final_min_route = 0;

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };



struct location {

	int x, y, route;

};



location findSmallRouteBFS(int x, int y, char factory) {

	memset(vis, 0, sizeof(vis));

	deque<location> que;

	location temp = { x,y,0 };

	que.push_back(temp);

	vis[x][y] = 1;

	while (!que.empty()) {

		location st = que.front();

		que.pop_front();

		if (mapT[st.x][st.y] == factory) {

			return st;

		}

		for (int i = 0; i < 4; ++i) {

			int t_x = st.x + dir[i][0];

			int t_y = st.y + dir[i][1];

			if (t_x < 0 || t_x >= H || t_y < 0 || t_y >= W || mapT[t_x][t_y] == 'X') {

				continue;

			}

			location temp = { t_x,t_y,st.route + 1 };

			if (!vis[t_x][t_y]) {

				vis[t_x][t_y] = 1;

				que.push_back(temp);

			}

		}

	}



}



int main() {

	cin >> H >> W >> N;

	for (int i = 0; i < H; i++) {

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

			cin >> temp;

			mapT[i][j] = temp;

			if (temp == 'S') {

				mapT[i][j] = '0';

				temp_x = i;

				temp_y = j;

			}

		}

	}



	for (int factory = 1; factory != N + 1; ++factory) {



		location lo = findSmallRouteBFS(temp_x, temp_y, mapT[temp_x][temp_y] + 1);

		temp_x = lo.x;

		temp_y = lo.y;

		final_min_route += lo.route;

	}



	cout << final_min_route << endl;

	//system("pause");

	return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<queue>

using namespace std;



typedef struct{

 int x;

 int y;

}P;//表示坐?



char graph[1000][1000];

P aim[10];

P s,g;//s起点，g?点

int N,W,H;

int vis[1000][1000]; //用来存?距?

int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



int bfs(P s,P g);



int main(){

    int i,j,t,step=0;

    cin>>H>>W>>N;

    

    for(i=0;i<H;i++)

    for(j=0;j<W;j++){

        cin>>graph[i][j];

      if(graph[i][j]<='9'&&graph[i][j]>='1'){ 

         t=graph[i][j]-'0';

         aim[t].x=i;

         aim[t].y=j;

      } //把1-N的坐?保存在 aim数?中 

      else if(graph[i][j]=='S'){

          s.x=i;

          s.y=j;

          graph[i][j]='.';

      }//得到最初的起点 

    }

    

    for(i=1;i<=N;i++){

       g.x=aim[i].x;

       g.y=aim[i].y;//1-N ，从小到大，?次把一个 作??点 

       step+=bfs(s,g);

       s.x=g.x;

       s.y=g.y;//到??个?点后??点?起点 

       graph[g.x][g.y]='.';

    }

   

    cout<<step<<endl;

}



int bfs(P s,P g){

    queue<P> que;

      P n;

    

    for(int i=0;i<H;i++)

    for(int j=0;j<W;j++)

     vis[i][j]=-1;

     

     que.push(s);

     vis[s.x][s.y]=0;

     

     while(que.size()){

         

       P p=que.front();

         que.pop();

       if(p.x==g.x&&p.y==g.y)

       break;

       

       for(int i=0;i<4;i++){

           n.x=p.x+dx[i];

           n.y=p.y+dy[i];//向四方漫射 

        if(0<=n.x&&n.x<H&&0<=n.y&&n.y<W&&graph[n.x][n.y]!='X'&&vis[n.x][n.y]==-1){

               que.push(n);

               vis[n.x][n.y]=vis[p.x][p.y]+1;

           }

       }

   }

     return vis[g.x][g.y];

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<algorithm>

#include<vector>

#include<string.h>

#include<string.h>

#include<functional>

//aoj 0558

using namespace std;

int n,bs;

int hs,sl;

int dh[5]={0,0,0,1,-1};

int dll[5]={0,1,-1,0,0};

int cun[1003][1003];

struct pt{

	int hh;

	int ll;

	int step;

};

pt dl1[11];

char vis[1003][1003];

pt dl[1<<16];

void bfs(int h,int l,int gs)

{

	int qy=1<<16;

	qy--;

	memset(dl,0,sizeof(dl));

	memset(vis,0,sizeof(vis));

	int front=1;

	int back=2;

	pt ls;

	ls.hh=h;

	ls.ll=l;

	ls.step=0;

	dl[1]=ls;

	vis[h][l]=1;

	while(front<back)

	{

		pt lss=dl[front&qy];

		front++;

		for(int i=1;i<=4;i++)

		{

			if(lss.hh+dh[i]>0&&lss.hh+dh[i]<=hs&&lss.ll+dll[i]>0&&lss.ll+dll[i]<=sl&&cun[lss.hh+dh[i]][lss.ll+dll[i]]!=111&&vis[lss.hh+dh[i]][lss.ll+dll[i]]!=1)

			{

				pt jr;

				jr.hh=lss.hh+dh[i];

				jr.ll=lss.ll+dll[i];

				jr.step=lss.step+1;

				if(cun[lss.hh+dh[i]][lss.ll+dll[i]]==gs)

				{

					bs+=jr.step;

					return;

				}else{

					dl[back&qy]=jr;

					vis[jr.hh][jr.ll]=1;

					back++;

				}

			}

		}

	}

}

int main()

{

	scanf("%d%d%d",&hs,&sl,&n);

	while(getchar()!='\n');

	for(int i=1;i<=hs;i++)

	{

		for(int j=1;j<=sl;j++)

		{

			char aaa;

			scanf("%c",&aaa);

			if(aaa=='X')

			{

				cun[i][j]=111;

			}

			if(aaa=='S')

			{

				pt ls;

				ls.hh=i;

				ls.ll=j;

				dl1[0]=ls;

				cun[i][j]=22;

			}

			if(aaa>='1'&&aaa<='9')

			{

				pt ls;

				ls.hh=i;

				ls.ll=j;

				dl1[aaa-'0']=ls;

				cun[i][j]=aaa-'0';

			}

		}

		

		while(getchar()!='\n');

	}

	for(int i=0;i<=n-1;i++)

	{

		bfs(dl1[i].hh,dl1[i].ll,i+1);

	}

	printf("%d\n",bs);

	return 0;

}






















// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int h,w,n;

char mp[1003][1003];

char vis[1003][1003];

int ans;

struct pt{

	int x,y;

	int st;	

};

pt st;

pt dl[1000005];

int front,back;

pt cun[21];

int dx[5]={0,0,0,1,-1};

int dy[5]={0,1,-1,0,0};

void bfs(int a)

{

	front=back=1;

	dl[back]=cun[a];

	back++;

	memset(vis,0,sizeof(vis));

	while(front<back)

	{

		pt ls=dl[front];

		front++;

		if(mp[ls.x][ls.y]=='0'+a+1)

		{

			ans+=ls.st;

			break;	

		}

		for(int i=1;i<=4;i++)

		{

			int xx=ls.x+dx[i];

			int yy=ls.y+dy[i];

			if(xx>0&&yy>0&&xx<=h&&yy<=w)

			{

				if(mp[xx][yy]!='X'&&vis[xx][yy]==0)

				{

					dl[back]=(pt){xx,yy,ls.st+1};

					back++;

					vis[xx][yy]=1;	

				}

			}

		}

	}

}

int main()

{

	scanf("%d%d%d",&h,&w,&n);

	for(int i=1;i<=h;i++)

	{

		scanf("%s",mp[i]+1);

	}

	for(int i=1;i<=h;i++)

	{

		for(int j=1;j<=w;j++)

		{

			if(mp[i][j]=='S')

			{

				cun[0]=(pt){i,j,0};	

			}else if(mp[i][j]<'9'&&mp[i][j]>'0')

			{

				cun[mp[i][j]-'0']=(pt){i,j,0};	

			}

		}

	}

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

	{

		bfs(i);

	}

	printf("%d\n",ans);

	return 0;

}


















// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <stdio.h>

#include <cstring>

#include <queue>

using namespace std;



char ma[1005][1005];int vis[1005][1005];

int w,h,n;



int dx[]={1,0,-1,0};

int dy[]={0,1,0,-1};



struct node

{

    int x,y,time;

};

node start;



void bfs(char ed)

{

    queue<node> que;

    que.push(start);

    vis[start.x][start.y]=1;

    while(!que.empty())

    {

        node no=que.front();

        que.pop();

        for(int i=0;i<4;i++)

        {

            int x=no.x+dx[i];

            int y=no.y+dy[i];

            if(vis[x][y]||x>=h||x<0||y>=w||y<0||ma[x][y]=='X')

                continue;

            if(ma[x][y]==ed)

            {

                start.x=x;

                start.y=y;

                start.time=no.time+1;

                return ;

            }

            vis[x][y]=1;

            node no1;

            no1.x=x;no1.y=y;no1.time=no.time+1;

            que.push(no1);

        }

    }

}



int main()

{

    while(~scanf("%d %d %d", & h, & w, & n))

    {

        for(int i=0;i<h;i++)

        {

            scanf("%s",&ma[i]);

            for(int j=0;j<w;j++)

                if(ma[i][j]=='S')

                {

                    start.x=i;

                    start.y=j;

                    start.time=0;

                }



        }

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

            {

                memset(vis,0,sizeof(vis));

                bfs(i+'1');

            }



            printf("%d\n",start.time);

    }

    return 0; 

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

#include<map>

#include<queue>

using namespace std;

#define MAX 1005



int h, w, n;

char city[MAX][MAX];

struct node{

	int x,y,time;

} start;

int direc1[4] = { -1,0,1,0 }, direc2[4] = { 0,1,0,-1 };

map<int,int>visited;



void dfs(char end) {

	queue<node> que;

	que.push(start);

	visited[start.x*w+start.y]=1;

	int nextx,nexty;

	while (que.size()!=0)

	{

		node now=que.front();

		que.pop();

		for (int i = 0; i < 4; i++) {

			nextx=now.x + direc1[i];

			nexty=now.y+direc2[i];

			if (nextx >= 0 && nextx< h&&nexty>= 0 && nexty < w && city[nextx][nexty]!='X' && !visited[nextx*w+nexty]) {	



				if (city[nextx][nexty]==end)

				{

					start.x=nextx;

					start.y=nexty;

					start.time=now.time+1;

					return ;

				}

				else{

					visited[nextx*w+nexty]=1;

					node now1;

					now1.x=nextx;

					now1.y=nexty;

					now1.time=now.time+1;

					que.push(now1);

				}

			}

		}

	}



}







int main() {

	cin >> h >> w >> n;	

	for (int i = 0; i < h; i++)

	{

		for (int j = 0; j < w; j++)

		{

			cin >> city[i][j];

			if (city[i][j] == 'S') {

				start.x= i;

				start.y = j;

				start.time=0;

			}

		}

	}

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

		visited.clear();

		dfs(i+'1');

	}

	cout << start.time << endl;

	//system("pause");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rep(i,l,n) for(int i=l;i<n;i++)

#define rer(i,l,n) for(int i=l;i<=n;i++)

#define all(a) a.begin(),a.end()

#define o(a) cout<<a<<endl

#define pb(a) push_back(a)

#define mk(a,b) make_pair(a,b)

#define fi first

#define se second

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<int,int> pii;



int change(int h,int m,int s){

	return h*3600+m*60+s;

}



int main(){

	int n;

	while(1){

		cin>>n;

		if(n==0) break;

		int sh,sm,ss,th,tm,ts,ans=0;

		vi d(86410);

		rep(i,0,n){

			scanf("%d:%d:%d %d:%d:%d",&sh,&sm,&ss,&th,&tm,&ts);

			d[change(sh,sm,ss)]++; d[change(th,tm,ts)]--;

		}

		rer(i,1,86400){

			d[i]+=d[i-1]; ans=max(ans,d[i]);

		}

		o(ans);

	}

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define rep(i, a, n) for(int i = a; i < n; i++)

#define repb(i, a, b) for(int i = a; i >= b; i--)

#define all(a) a.begin(), a.end()

#define o(a) cout << a << endl

// #define int long long

#define fi first

#define se second

using namespace std;

typedef pair<int, int> P;



signed main(){

    int n;

    while(1){

        cin >> n;

        if(n == 0) break;

        int h, m, s, hh, mm, ss;

        int d[24 * 3600 + 100] = {};

        rep(i, 0, n){

            scanf("%d:%d:%d %d:%d:%d", &h, &m, &s, &hh, &mm, &ss);

            int st = h * 3600 + m * 60 + s;

            int ed = hh * 3600 + mm * 60 + ss;

            d[st]++; d[ed]--;

        }

        int MAX = 0;

        rep(i, 1, 24 * 3600 + 10){

            d[i] += d[i - 1];

            MAX = max(MAX, d[i]);

        }

        cout << MAX << endl;

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#define mp make_pair

#include<cstdio>

#define MAX 86400

#include<map>

#include<algorithm>

#include<cstdlib>

#include<string>

using namespace std;

typedef pair<int,int> P;

int main(){

	int n,l,a;

	char s[20];

	P table[20000];

	while(cin>>n,n){

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

			cin>>s;

			l=atoi(s)*3600+atoi(&s[3])*60+atoi(&s[6]);

			table[i]=P(l,1);

			cin>>s;

			a=atoi(s)*3600+atoi(&s[3])*60+atoi(&s[6]);

			table[i+n]=P(a,0);

		}

		int now=0,ans=0;

		sort(table,table+2*n);

		for(int i=0;i<2*n;i++){

			if(table[i].second)

			now++;

			else now--;

			ans=max(now,ans);

		}

		cout<<ans<<endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstdlib>

#include<map>

#include<algorithm>

#define mp make_pair

#include<iostream>

#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int,int> pi;

char in[20];

int n;

pi table[20000];

int main(){

	while(scanf("%d",&n),n){

		rep(i,n)rep(j,2){

			cin>>in;

			table[i*2+j]=mp(atoi(in)*3600+atoi(&in[3])*60+atoi(&in[6]),1-j);

		}

		sort(table,table+2*n);

		int ans=0,c=0;

		rep(i,2*n){

			if(table[i].second)

				c++;

			else c--;

			ans=max(ans,c);

		}

		printf("%d\n",ans);

	}

	return 0;

}

// Fastest known solution for this problem: