IITWPC4H - Maggu and Cuteness of Strings

no tags 

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

hide comments
Jacob Plachta: 2014-03-03 06:49:23

If s=t="abab", can we have w="ababbbaa", for example? This seems to meet the stated requirements, but I'm guessing it's intended that every character of w must belong to the subsequence for either s or t?

RE: Indeed, that value for w is not supposed to be valid, so the answer when s=t="abab" is 2 rather than 3. It would be nice to update the problem statement with stricter requirements!

---> thank you, Actually in the contest itself people had pointed out issues with that. But many people got intrepreted it the way I was wishing. Thank you for correction :)

Last edit: 2014-02-03 23:21:55

Added by:praveen123
Date:2014-02-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge