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 = ag.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.
}
}
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];
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewoKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCQlTY2FubmVyIGluID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKCQlpbnQgdGVzdHMgPSBJbnRlZ2VyLnBhcnNlSW50KGluLm5leHRMaW5lKCkpOwoJCQoJCWZvcihpbnQgaSA9IDA7IGkgPCB0ZXN0czsgaSsrKSB7CgkJCWludCBtYXggPSAwOwoJCQkKCQkJU3RyaW5nIGFnID0gaW4ubmV4dExpbmUoKTsKCQkJYWcgPSBhZy5yZXBsYWNlQWxsKCJcXHMiLCIiKTsKCQkJU3RyaW5nIHRvbSA9IGluLm5leHRMaW5lKCk7CgkJCXRvbSA9IHRvbS5yZXBsYWNlQWxsKCJcXHMiLCIiKTsKCQkJCgkJCXdoaWxlICghdG9tLmVxdWFscygiMCIpKSB7CgkJCQlpbnQgY3Jvc3MgPSBMQ1MoYWcsdG9tKTsKCQkJCW1heCA9IE1hdGgubWF4KGNyb3NzLCBtYXgpOwoJCQkJU3lzdGVtLm91dC5wcmludGxuKCJhZzogIiArIGFnKTsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbigidG9tOiAiICsgdG9tKTsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbigiY3Jvc3M6ICIgKyBjcm9zcyk7CgkJCQl0b20gPSBpbi5uZXh0TGluZSgpOwoJCQkJdG9tID0gdG9tLnJlcGxhY2VBbGwoIlxccyIsIiIpOwoJCQl9CgkJCQoJCQkvLyBQcmludCB0aGUgbWF4aW11bSBjb21tb24gY2hlY2twb2ludHMuCgkJCVN5c3RlbS5vdXQucHJpbnRsbihtYXggLSAxKTsKCQl9CgkJCgl9CgoJcHJpdmF0ZSBzdGF0aWMgaW50IExDUyhTdHJpbmcgeCwgU3RyaW5nIHkpIHsKICAgICAgICBpbnQgTSA9IHgubGVuZ3RoKCk7CiAgICAgICAgaW50IE4gPSB5Lmxlbmd0aCgpOwoKICAgICAgICAvLyBvcHRbaV1bal0gPSBsZW5ndGggb2YgTENTIG9mIHhbaS4uTV0gYW5kIHlbai4uTl0KICAgICAgICBpbnRbXVtdIG9wdCA9IG5ldyBpbnRbTSsxXVtOKzFdOwoKICAgICAgICAvLyBjb21wdXRlIGxlbmd0aCBvZiBMQ1MgYW5kIGFsbCBzdWJwcm9ibGVtcyB2aWEgZHluYW1pYyBwcm9ncmFtbWluZwogICAgICAgIGZvciAoaW50IGkgPSBNLTE7IGkgPj0gMDsgaS0tKSB7CiAgICAgICAgICAgIGZvciAoaW50IGogPSBOLTE7IGogPj0gMDsgai0tKSB7CiAgICAgICAgICAgICAgICBpZiAoeC5jaGFyQXQoaSkgPT0geS5jaGFyQXQoaikpCiAgICAgICAgICAgICAgICAgICAgb3B0W2ldW2pdID0gb3B0W2krMV1baisxXSArIDE7CiAgICAgICAgICAgICAgICBlbHNlIAogICAgICAgICAgICAgICAgICAgIG9wdFtpXVtqXSA9IE1hdGgubWF4KG9wdFtpKzFdW2pdLCBvcHRbaV1baisxXSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCgkJcmV0dXJuIG9wdFswXVswXTsKCX0KfQo=