Given two strings s and t of size n and m respectively. You can construct a string w of size n+m using s and t such that it should contain both s and t as its subsequences.

String w must satisfy this condition: For each character from 'a' to 'z', count of the character in w should be equal to sum of count in s and t. Additionally every character of w must belong to the subsequence for either s or t.

e.g. if s = ab and t = cd, Then w can be abcd, acbd, cdab, cabd, acdb, cadb. Note that adcb is not correct, As t is not a subsequence in it.

“Cuteness value” of a string is defined as the maximum length of consecutive equal characters in the string.

For all possible string w that you can construct, find out the maximum value of “Cuteness value”.

Input

First line contains T: number of test cases.

For each test you case you are given a single line containing two space separated strings s and t. (1 <= size(s), size(t) <= 10^5).

Both the strings s and t will have characters from 'a' to 'z' of English alphabet only.

Note: Sum of length of all the input string is less than 5*10^6.

Output

For each test case, output the answer as given in problem statement.

Example

Input:
1
ab ab

Output:
2