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.

Difficulty: interview

Starter code:

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)