import java.util.*;
public class Main {
public static void main
(String[] args
) { Scanner in
= new Scanner
(System.
in); int tests
= Integer.
parseInt(in.
nextLine());
for(int i = 0; i < tests; i++) {
int max = 0;
ag = g.replaceAll("\\s","");
tom = tom.replaceAll("\\s","");
while (!tom.equals("0")) {
int cross = LCS(ag,tom);
max
= Math.
max(cross, max
); System.
out.
println("ag: " + ag
); System.
out.
println("tom: " + tom
); System.
out.
println("cross: " + cross
); tom = in.nextLine();
tom = tom.replaceAll("\\s","");
}
// Print the maximum common checkpoints.
System.
out.
println(max
/2 - 1); }
}
int M = x.length();
int N = y.length();
// opt[i][j] = length of LCS of x[i..M] and y[j..N]
int[][] opt = new int[M+1][N+1];
// compute length of LCS and all subproblems via dynamic programming
for (int i = M-1; i >= 0; i--) {
for (int j = N-1; j >= 0; j--) {
if (x.charAt(i) == y.charAt(j))
opt[i][j] = opt[i+1][j+1] + 1;
else
opt
[i
][j
] = Math.
max(opt
[i
+1][j
], opt
[i
][j
+1]); }
}
return opt[0][0];
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewoKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCQlTY2FubmVyIGluID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKCQlpbnQgdGVzdHMgPSBJbnRlZ2VyLnBhcnNlSW50KGluLm5leHRMaW5lKCkpOwoJCQoJCWZvcihpbnQgaSA9IDA7IGkgPCB0ZXN0czsgaSsrKSB7CgkJCWludCBtYXggPSAwOwoJCQkKCQkJU3RyaW5nIGFnID0gaW4ubmV4dExpbmUoKTsKCQkJYWcgPSBnLnJlcGxhY2VBbGwoIlxccyIsIiIpOwoJCQlTdHJpbmcgdG9tID0gaW4ubmV4dExpbmUoKTsKCQkJdG9tID0gdG9tLnJlcGxhY2VBbGwoIlxccyIsIiIpOwoJCQkKCQkJd2hpbGUgKCF0b20uZXF1YWxzKCIwIikpIHsKCQkJCWludCBjcm9zcyA9IExDUyhhZyx0b20pOwoJCQkJbWF4ID0gTWF0aC5tYXgoY3Jvc3MsIG1heCk7CgkJCQlTeXN0ZW0ub3V0LnByaW50bG4oImFnOiAiICsgYWcpOwoJCQkJU3lzdGVtLm91dC5wcmludGxuKCJ0b206ICIgKyB0b20pOwoJCQkJU3lzdGVtLm91dC5wcmludGxuKCJjcm9zczogIiArIGNyb3NzKTsKCQkJCXRvbSA9IGluLm5leHRMaW5lKCk7CgkJCQl0b20gPSB0b20ucmVwbGFjZUFsbCgiXFxzIiwiIik7CgkJCX0KCQkJCgkJCS8vIFByaW50IHRoZSBtYXhpbXVtIGNvbW1vbiBjaGVja3BvaW50cy4KCQkJU3lzdGVtLm91dC5wcmludGxuKG1heC8yIC0gMSk7CgkJfQoJCQoJfQoKCXByaXZhdGUgc3RhdGljIGludCBMQ1MoU3RyaW5nIHgsIFN0cmluZyB5KSB7CiAgICAgICAgaW50IE0gPSB4Lmxlbmd0aCgpOwogICAgICAgIGludCBOID0geS5sZW5ndGgoKTsKCiAgICAgICAgLy8gb3B0W2ldW2pdID0gbGVuZ3RoIG9mIExDUyBvZiB4W2kuLk1dIGFuZCB5W2ouLk5dCiAgICAgICAgaW50W11bXSBvcHQgPSBuZXcgaW50W00rMV1bTisxXTsKCiAgICAgICAgLy8gY29tcHV0ZSBsZW5ndGggb2YgTENTIGFuZCBhbGwgc3VicHJvYmxlbXMgdmlhIGR5bmFtaWMgcHJvZ3JhbW1pbmcKICAgICAgICBmb3IgKGludCBpID0gTS0xOyBpID49IDA7IGktLSkgewogICAgICAgICAgICBmb3IgKGludCBqID0gTi0xOyBqID49IDA7IGotLSkgewogICAgICAgICAgICAgICAgaWYgKHguY2hhckF0KGkpID09IHkuY2hhckF0KGopKQogICAgICAgICAgICAgICAgICAgIG9wdFtpXVtqXSA9IG9wdFtpKzFdW2orMV0gKyAxOwogICAgICAgICAgICAgICAgZWxzZSAKICAgICAgICAgICAgICAgICAgICBvcHRbaV1bal0gPSBNYXRoLm1heChvcHRbaSsxXVtqXSwgb3B0W2ldW2orMV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAoJCXJldHVybiBvcHRbMF1bMF07Cgl9Cn0K