Longest Common Subsequence

Given two strings, your task is to determine their longest common subsequence (LCS). A subsequence is defined as a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For each test case, you will be provided with two strings and you must compute and output their LCS. In cases where multiple LCS solutions exist, output any one of them. This problem is a classical application of dynamic programming and backtracking.

inputFormat

The first line contains an integer T, the number of test cases. Each test case consists of exactly two lines. The first line of a test case contains the string S1 and the second line contains the string S2. Note that the strings may be empty.

outputFormat

For each test case, output a single line containing the longest common subsequence of the two provided strings.

2
AGGTAB
GXTXAYB
ABCDGH
AEDFHR

GTAB
ADH