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

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <iomanip>

//#include <string.h>

#include <bits/stdc++.h>

#define INF 999999999

using namespace std;

#define ll long long

#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int vis[1000000]={0};

int hh[1000000];

int main()

{

    boost;

    int n;

    cin >>n;

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

        cin >>hh[i];

    }

    int j=1,sum=0,falg=0,p=1;

    vis[1]=1;

    while(1){

        if(vis[2]==1)

            break;

        else if(vis[j]==2){

            cout<<-1<<endl;

            falg=1;

            break;

        }

        else {

            j=hh[j];

            //cout<<j<<endl;

            vis[j]++;

            //cout<<" "<<vis[j]<<endl;

            sum++;

        }

    }

    if(!falg)

        cout<<sum<<endl;

    return 0;



}


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

int a[100003];

int main()

{

	long long b,c,d;

	scanf("%lld",&b);

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

	{

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

	} 

	c=a[1];

	if(c==2) printf("1");

	else {

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

	{

	d=a[c];

	if(d==2) 

	{

	printf("%d",i+1);

	break;

   }

	c=d;

	if(i==b-1){

     

	printf("-1");

	break;

	}       

}

}

	return 0;

}

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

using namespace std;



int a[100000];

int main()

{

	int N;

	int i = 1;

	int j =0;

	int ini = 1;

	int flag = 0;

	cin>>N;

	int k = N;



	while(k--)

	{

		cin>>a[i++]; 

	}



	do{

		j++;

		if(a[ini]==2)

		{

			flag=1;

		}

		else

			ini = a[ini];

	

	}while(j<=N&&flag==0);

	if(flag==0)

		cout<<-1<<endl;

	else

		cout<<j<<endl;

	return 0;

}

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

int a[100003];

int main()

{

	long long b,c,d;

	scanf("%lld",&b);

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

	{

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

	} 

	c=a[1];

	if(c==2) printf("1");

	else {

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

	{

	d=a[c];

	if(d==2) 

	{

	printf("%d",i+1);

	break;

   }

	c=d;

	if(i==b-1){

     

	printf("-1");

	break;

	}       

}

}

	return 0;

}

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

#include <string>

#include <vector>

#include <algorithm>



#define ll long long

using namespace std;



ll N;

vector<ll> a;





int main(){

  ll inp;

  ll num=1;

  ll result=0;

  

  cin >> N;

  int checked[100000]={0};

  

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

    cin >> inp;

    a.push_back(inp);

  }

  

  do{

    result++;

    if(a[num-1]==2){

      cout << result << endl;

      return 0;

    }

    else{

      checked[num-1]=1;

      num=a[num-1];

    }

  }while(!checked[num-1]);



  cout << "-1" << endl;

  return 0;

  

}


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

#include <iomanip>

#include <vector>

#include <algorithm>

#include <cstring>

#include <map>

#include <queue>

#include <cmath>

#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3

using namespace std;



#define MOD 1000000007

#define ll long long

#define ld long double

#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)

#define rep(i,n) FOR(i,0,n)

#define pb push_back

#define mp make_pair

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

#define rall(a) a.rbegin(),a.rend()

#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())

#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}

template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}

ll lcm(ll a, ll b){return a/gcd(a,b)*b;}







bool check[100005];

int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);



  ll N; cin >> N ;



  vector<ll> A; 

  rep(i,N){

    ll inp; cin >> inp;

    A.pb(inp);

  }



  ll push = 1;

  rep(i,N){

    push--;

    if(push==1){ cout << i << endl; return 0;}

    push = A[push];

    if(check[push]) break;

    check[push] = true;

  }



  cout << "-1" << endl;



  

  

  //cout << fixed << setprecision(16) << ans << endl;

  

  return 0;

}


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

#include<cstring>

const int MAXN = 100000;

const int MAXK = 1000;

int x[MAXN + 5], y[MAXN + 5], c[MAXN + 5];

int y1[10 * MAXK + 5];

int main() 

{

	int N,K,Max=0,cnt = 0;

	scanf("%d%d",&N,&K);

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

	{

		char ch;

		scanf("%d%d %c",&x[i],&y[i],&ch);

		x[i]= x[i] % (2*K);

		y[i]= y[i] % (2*K);

		if(ch=='W' ) c[i] = 1;

		else c[i]=0;

	}

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

		cnt = 0;

		memset(y1,0,sizeof(y1));

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

			bool p = ( i <= x[j] && x[j] < i+K );

			bool q = ( 0 <= y[j] && y[j] < K );

			if( p ^ q == c[j] )

			{

				cnt++;

				y1[y[j]] ++;

			}

			else 

			{

				y1[y[j]] --;

			}

		}

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

		{

			if(cnt>Max) 

				Max = cnt;

			if(N-cnt>Max ) 

				Max=N-cnt;

			if( j != K )

				cnt = cnt - y1[j] - y1[K+j];

		}

	}

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

}


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

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXN = 100000;

int x[MAXN + 5], y[MAXN + 5], c[MAXN + 5];

int y1[MAXN],N,K,Max,cnt;

int main() 

{



	scanf("%d%d",&N,&K);

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

	{

		char ch;

		scanf("%d %d %c",&x[i],&y[i],&ch);

		x[i]%=(2*K);

		y[i]%=(2*K);

		if(ch=='W' ) c[i] = 1;

	}

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

		cnt = 0;

		fill(y1,y1+2*K+1,0);

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

			bool p = ( i <= x[j] && x[j] < i+K );

			bool q = ( 0 <= y[j] && y[j] < K );

			if( p ^ q == c[j] )

			{

				cnt++;

				y1[y[j]] ++;

			}

			else 

			{

				y1[y[j]] --;

			}

		}

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

		{

			Max=std::max(Max,std::max(cnt,N-cnt));

			if( j != K )

				cnt = cnt - y1[j] - y1[K+j];

		}

	}

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

}


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

#include<algorithm>

#include<cstring>

const int MAXN = 100000;

const int MAXK = 1000;

int x[MAXN + 5], y[MAXN + 5], c[MAXN + 5];

int y1[10 * MAXK + 5];

int main() 

{

	int N,K,Max=0,cnt = 0;

	scanf("%d%d",&N,&K);

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

	{

		char ch;

		scanf("%d%d %c",&x[i],&y[i],&ch);

		x[i]= x[i] % (2*K);

		y[i]= y[i] % (2*K);

		if(ch=='W' ) c[i] = 1;

		else c[i]=0;

	}

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

		cnt = 0;

		memset(y1,0,sizeof(y1));

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

			bool p = ( i <= x[j] && x[j] < i+K );

			bool q = ( 0 <= y[j] && y[j] < K );

			if( p ^ q == c[j] )

			{

				cnt++;

				y1[y[j]] ++;

			}

			else 

			{

				y1[y[j]] --;

			}

		}

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

		{

			Max=std::max(Max,std::max(cnt,N-cnt));

			if( j != K )

				cnt = cnt - y1[j] - y1[K+j];

		}

	}

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

}


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

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXN = 100000;

int x[MAXN + 5], y[MAXN + 5], c[MAXN + 5];

int y1[MAXN],N,K,Max,cnt;

int main() 

{



	scanf("%d%d",&N,&K);

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

	{

		char ch;

		scanf("%d %d %c",&x[i],&y[i],&ch);

		x[i]%=(2*K);

		y[i]%=(2*K);

		if(ch=='W' ) c[i] = 1;

	}

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

		cnt = 0;

		fill(y1,y1+2*K+1,0);

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

			bool p = ( i <= x[j] && x[j] < i+K );

			bool q = ( 0 <= y[j] && y[j] < K );

			if( p ^ q == c[j] )

			{

				cnt++;

				y1[y[j]] ++;

			}

			else 

			{

				y1[y[j]] --;

			}

		}

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

		{

			Max=std::max(Max,std::max(cnt,N-cnt));

			if( j != K )

				cnt = cnt - y1[j] - y1[K+j];

		}

	}

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

}


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

#include<cstring>

const int MAXN = 100000;

const int MAXK = 1000;

int x[MAXN + 5], y[MAXN + 5], c[MAXN + 5];

int y1[10 * MAXK + 5];

int main() {

	int N, K, Max = 0, cnt = 0;

	scanf("%d%d",&N,&K);

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

		char ch;

		scanf("%d%d %c",&x[i],&y[i],&ch);

		x[i] = x[i] % (2*K);

		y[i] = y[i] % (2*K);

		if( ch == 'W' ) c[i] = 1;

		else c[i] = 0;

	}

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

		cnt = 0;

		memset(y1,0,sizeof(y1));

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

			int p = ( i <= x[j] && x[j] < i+K );

			int q = ( 0 <= y[j] && y[j] < K );

			if( p ^ q == c[j] ){

				cnt++;

				y1[y[j]] ++;

			}

			else {

				y1[y[j]] --;

			}

		}

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

			if( cnt > Max ) Max = cnt;

			if( N - cnt > Max ) Max = N - cnt;

			if( j != K )

				cnt = cnt - y1[j] - y1[K+j];

		}

	}

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

}

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

#include<algorithm>

using namespace std;

#define N 100000

int x[N+5],y[N+5],c[N+5],y1[N+5];

int n,k,ans,cnt;

int main()

{

	scanf("%d%d",&n,&k);

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

	{

		char ch;

		scanf("%d %d %c",&x[i],&y[i],&ch);

		x[i]%=(2*k);

		y[i]%=(2*k);

		if(ch=='W')

			c[i]=1;

	}

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

	{

		cnt=0;

		fill(y1,y1+2*k+1,0);

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

		{

			bool p=(i<=x[j]&&x[j]<i+k);

			bool q=(0<=y[j]&&y[j]<k);

			if(p^q==c[j])

				cnt++,y1[y[j]]++;

			else

				y1[y[j]]--;

		}

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

		{

			ans=max(max(cnt,n-cnt),ans);

			if(j!=k)

				cnt=cnt-y1[j]-y1[k+j];

		}

	}

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

}


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

#include<algorithm>

#include<cstring>

using namespace std;

int n,k;

int x[100001],y[100001];

bool c[100001];

char s;

int h[10001];

int  main()

{

	scanf("%d%d",&n,&k);

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

	{

		scanf("%d%d %c",&x[i],&y[i],&s);

		x[i]=x[i]%(2*k);

		y[i]=y[i]%(2*k);

		if(s=='B')

			c[i]=1;

	}

	int maxn=0,cnt;

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

	{

		cnt=0;

		memset(h,0,sizeof(h));

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

		{

			int p=(i<=x[j]&&x[j]<i+k);

			int q=(0<=y[j]&&y[j]<k);

			if(p^q==c[j])

			{

				cnt++;

				h[y[j]]++;

			}

			else

				h[y[j]]--;

		}

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

		{

			maxn=max(max(cnt,n-cnt),maxn);

			if(j!=k)

				cnt=cnt-h[j]-h[k+j];

		}

	}

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

}

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

#include<algorithm>

using namespace std;

#define N 100000

int x[N+5],y[N+5],c[N+5],y1[N+5];

int n,k,ans,cnt;

int main()

{

	scanf("%d%d",&n,&k);

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

	{

		char ch;

		scanf("%d %d %c",&x[i],&y[i],&ch);

		x[i]%=(2*k);

		y[i]%=(2*k);

		if(ch=='W')

			c[i]=1;

	}

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

	{

		cnt=0;

		fill(y1,y1+2*k+1,0);

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

		{

			bool p=(i<=x[j]&&x[j]<i+k);

			bool q=(0<=y[j]&&y[j]<k);

			if(p^q==c[j])

				cnt++,y1[y[j]]++;

			else

				y1[y[j]]--;

		}

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

		{

			ans=max(max(cnt,n-cnt),ans);

			if(j!=k)

				cnt=cnt-y1[j]-y1[k+j];

		}

	}

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

}


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




#include<bits/stdc++.h>

using namespace std;

#define MAX 100005

#define INF (1e9+1)

 

int n,W;

int dp[MAX];

 

int main(){

  fill(dp,dp+MAX,INF);

  dp[0]=0;

   

  cin>>n>>W;

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

    int v,w;

    cin>>v>>w;

    for(int j=MAX-1;j>=v;j--){

      dp[j]=min(dp[j],dp[j-v]+w);

    }

  }

 

  for(int i=MAX-1;i>=0;i--){

    if(dp[i]<=W){

      cout<<i<<endl;

      break;

    }

  }

   

  return 0;

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

 

int main()

{

    int i,j,N,v[100],ans;

    long long w[100],W,dp[101][10001];

     

    cin >> N >> W;

     

    for(i=0;i<=N-1;i++) cin >> v[i] >> w[i];

     

    for(i=0;i<=100*N;i++) dp[0][i]=1000000001;

    dp[0][0]=0;

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

    {

        for(j=0;j<=N*100;j++)

        {

            if(j-v[i-1]>=0) dp[i][j]=min(dp[i-1][j], dp[i-1][j-v[i-1]]+w[i-1]);

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

        }

    }

    for(i=0;i<=N*100;i++)

    {

        if(dp[N][i]<=W) ans=i;

    }

    cout << ans << endl;

    return 0;

}


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

using namespace std;

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



vector<vector<int> > DP(1000,vector<int>(1000));



void init(int n,int m){

    rep(i,n){

        rep(j,m){DP[i][j]=-1;}

    }

}



int LCS(char a[],char b[],int n,int m){

    if(n<0||m<0)return 0;

    if(DP[n][m]!=-1)return DP[n][m];

    if(a[n]==b[m])return DP[n][m]=1+LCS(a,b,n-1,m-1);

    return DP[n][m]=max(LCS(a,b,n-1,m),LCS(a,b,n,m-1));

}



int main(){

    int q;cin>>q;

    char s[1001],t[1001];

    rep(i,q){

        cin>>s>>t;

        int n=strlen(s),m=strlen(t);

        init(n,m);

        int ans=LCS(s,t,n-1,m-1);

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

    }

}


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

using namespace std;

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



int LCS(string a,string b){

    int n1=a.size(),n2=b.size();

    int DP[n1+1][n2+1];

    DP[0][0]=0;

    rep(i,n1)DP[i+1][0]=0;

    rep(i,n2)DP[0][i+1]=0;

    rep(i,n1){

        rep(j,n2){

            if(a[i]==b[j])DP[i+1][j+1]=1+DP[i][j];

            else DP[i+1][j+1]=max(DP[i][j+1],DP[i+1][j]);

        }

    }

    return DP[n1][n2];

}



int main(){

    int q;cin>>q;

    string s,t;

    rep(i,q){

        cin>>s>>t;

        int ans=LCS(s,t);

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

    }

}


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

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

static const int N=1000;

int lcs(string X,string Y)

{

    int c[N+1][N+1];

    int m=X.size();

    int n=Y.size();

    int maxl=0;

    X=" "+X;

    Y=" "+Y;

    for(int i=0;i<=m;i++)c[i][0]=0;

    for(int j=0;j<=n;j++)c[0][j]=0;



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

      {

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

          {

              if(X[i]==Y[j])

                 {

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

                 }

                    else{

                        c[i][j]=max(c[i-1][j],c[i][j-1]);

                }

                    maxl=max(maxl,c[i][j]);

          }

      }

      return maxl;

}

int main()

{

    string s1,s2;

    int n;

    cin>>n;

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

    {

        cin>>s1>>s2;

        cout<<lcs(s1,s2)<<endl;

    }

    return 0;

}

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

#include <string.h>

#define N 1010

char a[N];

char b[N];

int dp[N][N];

//int LCS(int i, int j){

//    if(i == -1 || j == -1) return 0;

//    if(a[i] == b[j]) return LCS(i-1, j-1) + 1;

//    else return LCS(i-1, j) > LCS(i, j-1) ? LCS(i-1, j) : LCS(i, j-1);

//}

int main(){

    int k;

    scanf("%d", &k);

    while(k--){

        scanf("%s", a);

        scanf("%s", b);

        int n = strlen(a);

        int m = strlen(b);

        for(int i = n-1; i >= 0; i--) a[i+1] = a[i];

        for(int i = m-1; i >= 0; i--) b[i+1] = b[i];

        int max = n > m ? n : m;

        for(int i = 0; i <= max; i++) dp[0][i] = dp[i][0] = 0;

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

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

                if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;

                else {

                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];

                }

            }

        }

        printf("%d\n", dp[n][m]);

        //printf("%d\n", LCS(strlen(a)-1, strlen(b)-1));

    }

    return 0;

}


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

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;



const int maxn = 1000 + 5;

int dp[maxn][maxn];

char x[maxn];

char y[maxn];



int main()

{

    int q;

    scanf("%d", &q);

    while (q--)

    {

        scanf("%s %s", x + 1, y + 1);

        memset(dp, 0, sizeof(dp));

        int m = strlen(x + 1);

        int n = strlen(y + 1);

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

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

            {

                if (x[i] == y[j])

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

                else

                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

            }

        printf("%d\n", dp[m][n]);

    }

    return 0;

}




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

#include <string.h>

#define N 1010

char a[N];

char b[N];

int dp[N][N];

//int LCS(int i, int j){

//    if(i == -1 || j == -1) return 0;

//    if(a[i] == b[j]) return LCS(i-1, j-1) + 1;

//    else return LCS(i-1, j) > LCS(i, j-1) ? LCS(i-1, j) : LCS(i, j-1);

//}

int main(){

    int k;

    scanf("%d", &k);

    while(k--){

        scanf("%s", a);

        scanf("%s", b);

        int n = strlen(a);

        int m = strlen(b);

        for(int i = n-1; i >= 0; i--) a[i+1] = a[i];

        for(int i = m-1; i >= 0; i--) b[i+1] = b[i];

        int max = n > m ? n : m;

        for(int i = 0; i <= max; i++) dp[0][i] = dp[i][0] = 0;

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

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

                if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;

                else {

                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];

                }

            }

        }

        printf("%d\n", dp[n][m]);

        //printf("%d\n", LCS(strlen(a)-1, strlen(b)-1));

    }

    return 0;

}


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

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<stack>

#include<queue>

#include<vector>

#include<algorithm>

#include<string>

#include<iostream>

using namespace std;

static const int N=1000;

/*int max(int a,int b){

    if(a>b)return a;else return b;

}*/

int lcs(string X,string Y){

    int c[N+1][N+1];

    int m=X.size();

    int n=Y.size();

    int maxl=0;

    X=' '+X;

    Y=' '+Y;

    for(int i=0;i<=m;i++)c[i][0]=0;

    for(int j=1;j<=n;j++)c[0][j]=0;

    

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

        for(int j=1;j<=n;j++){

            if(X[i]==Y[j]){

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

            }else{

                c[i][j]=max(c[i-1][j],c[i][j-1]);

            }

            maxl=max(maxl,c[i][j]);

        }

    }

    return maxl;

}



int main(){

    string s1,s2;

    int n;cin>>n;

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

        cin>>s1>>s2;

        cout<<lcs(s1,s2)<<endl;

    }

    return 0;

}

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




#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<stack>

#include<queue>

#include<vector>

#include<algorithm>

#include<string>

#include<iostream>

using namespace std;

typedef long long ll;

int mod(ll a){

    int c=a%1000000007;

    if(c>=0)return c;

    else return c+1000000007;

}

typedef pair<int,int> i_i;





int main(){

    int q;cin>>q;

    while(q){

        char s[1005],t[1005];cin>>s>>t;

        ll ls=strlen(s),lt=strlen(t);

        for(ll i=ls-1;i>=0;i--)s[i+1]=s[i];

        for(ll j=lt-1;j>=0;j--)t[j+1]=t[j];

        int dp[ls+1][lt+1];

        for(int i=0;i<=ls;i++)dp[i][0]=0;

        for(int j=0;j<=lt;j++)dp[0][j]=0;

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

            for(int j=1;j<=lt;j++){

                if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;

                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

            }

        }

        cout<<dp[ls][lt]<<endl;

        q--;

    }

    

    return 0;

}














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

#include <string>

#include <algorithm>

using namespace std;

int dp[1002][1002];



int main(){

	int n;cin >> n;

	string x, y;

	while(n--){

		fill((int*)dp, (int*)(dp+1002), 0);

		cin >> x >> y;

		for(int i = 1;i <= x.size();i++){

			for(int j = 1;j <= y.size();j++){

				if(x[i-1] == y[j-1])dp[i][j] = dp[i-1][j-1] + 1;

				else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

			}

		}

		cout << dp[x.size()][y.size()] << endl;

	}

	return 0;

}

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

#include <string>

#include <algorithm>

using namespace std;

int dp[1002][1002];



int main(){

	int n;cin >> n;

	string x, y;

	while(n--){

		cin >> x >> y;

		for(int i = 1;i <= x.size();i++){

			for(int j = 1;j <= y.size();j++){

				if(x[i-1] == y[j-1])dp[i][j] = dp[i-1][j-1] + 1;

				else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

			}

		}

		cout << dp[x.size()][y.size()] << endl;

	}

	return 0;

}

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

#include <vector>

#include <string>

#include <cmath>

#include <set>

#include <algorithm>

#include <array>

#include <complex>

#include <utility>

#include <map>

#include <inttypes.h>



int LCS(std::string s, std::string t){

    int n, m, c[1001][1001] = {0};

    n = s.size();

    m = t.size();

    int maxlen = 0;

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

        c[i][0] = 0;

    }

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

        c[0][i] = 0;

    }

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

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

            if(s[i - 1] == t[j - 1]){

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

            }

            else{

                c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);

            }

            maxlen = std::max(maxlen, c[i][j]);

        }

    }

    return maxlen;

}

int main(){

    int N;



    std::cin >> N;

    std::string s1, s2;

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

        std::cin >> s1 >> s2;

        std::cout << LCS(s1, s2) << std::endl;

    }

    return 0;

}


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

#include <vector>

#include <string>

#include <cmath>

#include <set>

#include <algorithm>

#include <array>

#include <complex>

#include <utility>

#include <map>

#include <inttypes.h>

int c[1001][1001] = {0};

/*int LCS(std::string s, std::string t){

    int n, m, c[1001][1001] = {0};

    n = s.size();

    m = t.size();

    int maxlen = 0;

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

        c[i][0] = 0;

    }

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

        c[0][i] = 0;

    }

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

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

            if(s[i - 1] == t[j - 1]){

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

            }

            else{

                c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);

            }

            maxlen = std::max(maxlen, c[i][j]);

        }

    }

    return maxlen;

}*/

int main(){

    int N;



    std::cin >> N;

    std::string s1, s2;

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

        std::cin >> s1 >> s2;

        int n, m;

        n = s1.size();

        m = s2.size();

        int maxlen = 0;

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

            c[i][0] = 0;

        }

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

            c[0][i] = 0;

        }

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

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

                if(s1[i - 1] == s2[j - 1]){

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

                }

                else{

                    c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);

                }

                maxlen = std::max(maxlen, c[i][j]);

            }

        }

        std::cout << maxlen << std::endl;

    }

    return 0;

}


// Fastest known solution for this problem: