{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"A palindrome is a string that is identical to its reverse. For example, \"aba\", \"abba\", \"a\" and \"aa\" are palindromes, while \"ab\", \"abb\" and \"xyz\" are not.\r\n\r\nA string $X$ is called a substring of string $Y$ if it is possible to obtain $X$ by erasing some (possibly zero) characters from the beginning of $Y$ and some (possibly zero) from the end of $Y$ without changing the order of the remaining characters. For example, \"cp\" is a substring of \"icpc\", while \"icc\" is not.\r\n\r\nYou are given two strings $s$ and $t$. Find the minimum length of a string (let\u0027s denote it by $w$) that satisfies the following conditions:\r\n- $w$ is a palindrome\r\n- $s$ and $t$ are substrings of $w$\r\n\r\n### Input\r\n- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\r\n- The first and only line of each test case contains two space-separated strings $s$ and $t$.\r\n\r\n### Output\r\nFor each test case, print a single line containing one integer - the minimum length of a palindrome that contains both $s$ and $t$ as substrings.\r\n\r\n### Constraints \r\n- $1 \\le T \\le 1,000$\r\n- $1 \\le |s|, |t| \\le 2,000$\r\n- $s$ and $t$ contain only lowercase English letters\r\n- the sum of the lengths of all the strings on the input does not exceed $4,000$\r\n\r\n### Example Input\r\n```\r\n4\r\na a\r\na b\r\nabc cb\r\nabbc ba\r\n```\r\n\r\n### Example Output\r\n```\r\n1\r\n3\r\n5\r\n7\r\n```\r\n\r\n### Explanation\r\n**Example case 1:** $s$ and $t$ are both \"a\", and \"a\" is also the shortest palindrome that contains both $s$ and $t$.\r\n\r\n**Example case 2:** One possible string $w$ is \"aba\", since there is no palindrome with length $1$ or $2$ that contains both \"a\" and \"b\".\r\n\r\n**Example case 3:** One possible string $w$ is \"abcba\".\r\n\r\n**Example case 4:** One possible string $w$ is \"abbcbba\".\r\n"}}]}