algo2017_week7_LCS

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ALL(o) (o).begin(),(o).end()
#define fo(n) for(int i=0;i<n;i++)
#define fos(n) for(int i=1;i<=n;i++)
#define MAX 700

string a , b;

int LCS(){
    int dp[a.size() + 1][b.size() + 1];

    for( int i = 0 ; i <= a.size() ; ++i ) dp[i][0] = 0;
    for( int i = 0 ; i <= b.size() ; ++i ) dp[0][i] = 0;

    fos( a.size() )
        for( int j = 1 ; j <= b.size() ; ++j )
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i-1][j-1] + 1 : max( dp[i][j-1] , dp[i-1][j] );

    return dp[a.size()][b.size()];
}


int main(){

    int T;

    cin >> T;

    while( T-- ){
        cin >> a >> b;
        cout << LCS() << endl;
    }

    return 0;
}