//config = { input: 'tmp', newline: '\r\n' }; // win
config = { input: '/dev/stdin', newline: '\n' }; // linux

line = require('fs').readFileSync(config.input, 'ascii')
  .trim()
  .split(config.newline);

const MAXSIZE = 1000;
max = new Array(MAXSIZE);
for (i = 0; i < MAXSIZE; i++) {
  max[i] = new Array(MAXSIZE);
  for (j = 0; j < MAXSIZE; j++) max[i][j] = 0;
}

function lcs(X, Y, max) {
  var idx0, i, j;

  idx0 = X.indexOf(Y[0]);
  if (idx0 === -1) idx0 = X.length;
  for (i = 0; i < idx0; i++) max[i][0] = 0;
  for (i = idx0; i < X.length; i++) max[i][0] = 1;

  idx0 = Y.indexOf(X[0]);
  if (idx0 === -1) idx0 = Y.length;
  for (j = 1; j < idx0; j++) max[0][j] = 0;
  for (j = idx0; j < Y.length; j++) max[0][j] = 1;

  for (i = 1; i < X.length; i++) {
    for (j = 1; j < Y.length; j++) {
      max[i][j] = Math.max(max[i-1][j], max[i][j-1]);
      if (X[i] === Y[j])
        max[i][j] = Math.max(max[i][j], max[i-1][j-1]+1);
    }
  }
  return max[X.length-1][Y.length-1];
}

for (i = 1; i < line.length; i += 2) {
  console.log(lcs(line[i], line[i+1], max));
}