A pair of strings $(α, β)$ is called a subpair of a string $x$ if $x$ = $x_1+$$α+$$x_2+$$β+$$x_3$ (where a+b means concatenation of strings a and b) for some (possibly empty) strings $x1, x2$ and $x3$. We are given two strings and we need to find one subpair from each string such that : 
Let $(a,b) , (c,d) $be subpair of $string1$ and $string2$ respectively and $X$ $=$ $a$ + $b$ + $c$ + $d$
- $X$ is a palindrome
- $|a| = |d|$
- $|b| = |c|$
- $|X|$ is maximum

-----Input Format:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, two strings str1, str2. 

-----Output Format:-----
- For each testcase, output in a single line representing the length of palindrome |X|.

-----Constraints-----
- $1 \leq T \leq 5$
- $2 \leq |str1| \leq 10^3$
- $2 \leq |str2| \leq 10^3$

-----Sample Input 1:-----
1
abgcd dchbag

-----Sample Output 1:-----
8

-----Sample Input 2:-----
4   

aaa aaa

zaaax yaaaw

zax yaw

zx yw

-----Sample Output 2:-----
6

6

2

0  

-----EXPLANATION:-----
Sample Testcase 1: The subpairs are ("ab","cd") and ("dc","ba"). When the subpairs are concatenated string is "abcddcba" which is a pallindrome , |"ab"| = |"ba"|, |"cd"| = |"dc"| and has the maximum length equal to 8.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import defaultdict as dd

def find(a, b):
	n = len(a)
	m = len(b)
	dp = [[0] * (m + 1) for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if a[i] == b[j]:
				dp[i][j] = dp[i + 1][j + 1] + 1
	mx = dd(int)
	ans = 0
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			a = mx[i + 1, j]
			b = mx[i, j + 1]
			mx[i, j] = max([dp[i][j], a, b])
	for i in range(n):
		for j in range(m):
			c = dp[i][j]
			nxt = mx[i + c, j + c]
			cur = c + nxt
			ans = max(ans, cur)
	return 2 * ans
for case in range(int(input())):
	(a, b) = input().split()
	b = b[-1::-1]
	ans = find(a, b)
	print(ans)