You are given the strings $$$a$$$ and $$$b$$$, consisting of lowercase Latin letters. You can do any number of the following operations in any order:

if $$$|a| \gt 0$$$ (the length of the string $$$a$$$ is greater than zero), delete the first character of the string $$$a$$$, that is, replace $$$a$$$ with $$$a_2 a_3 \ldots a_n$$$;
if $$$|a| \gt 0$$$, delete the last character of the string $$$a$$$, that is, replace $$$a$$$ with $$$a_1 a_2 \ldots a_{n-1}$$$;
if $$$|b| \gt 0$$$ (the length of the string $$$b$$$ is greater than zero), delete the first character of the string $$$b$$$, that is, replace $$$b$$$ with $$$b_2 b_3 \ldots b_n$$$;
if $$$|b| \gt 0$$$, delete the last character of the string $$$b$$$, that is, replace $$$b$$$ with $$$b_1 b_2 \ldots b_{n-1}$$$.

Note that after each of the operations, the string $$$a$$$ or $$$b$$$ may become empty.

For example, if $$$a=$$$"hello" and $$$b=$$$"icpc", then you can apply the following sequence of operations:

delete the first character of the string $$$a$$$ $$$\Rightarrow$$$ $$$a=$$$"ello" and $$$b=$$$"icpc";
delete the first character of the string $$$b$$$ $$$\Rightarrow$$$ $$$a=$$$"ello" and $$$b=$$$"cpc";
delete the first character of the string $$$b$$$ $$$\Rightarrow$$$ $$$a=$$$"ello" and $$$b=$$$"pc";
delete the last character of the string $$$a$$$ $$$\Rightarrow$$$ $$$a=$$$"ell" and $$$b=$$$"pc";
delete the last character of the string $$$b$$$ $$$\Rightarrow$$$ $$$a=$$$"ell" and $$$b=$$$"p".

For the given strings $$$a$$$ and $$$b$$$, find the minimum number of operations for which you can make the strings $$$a$$$ and $$$b$$$ equal. Note that empty strings are also equal.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains the string $$$a$$$ ($$$1 \le |a| \le 20$$$), consisting of lowercase Latin letters.

The second line of each test case contains the string $$$b$$$ ($$$1 \le |b| \le 20$$$), consisting of lowercase Latin letters.

Output

For each test case, output the minimum number of operations that can make the strings $$$a$$$ and $$$b$$$ equal.

Double-ended Strings

Examples