IITWPC4H  Maggu and Cuteness of Strings
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.
eg. 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
vivek_dwivedi:
20180615 19:05:30
question is easy af! did it in o(n). dont know how people solved in 0.0!!


dark_lord1:
20160331 16:34:56
Extremely easy problem..Don't think complex, keep it simple..No DP..


anonymous:
20140303 06:49:23
Last edit: 20140321 19:34:40 

aqfaridi:
20140303 06:49:23
WTF .. s and t can contain other characters too. [cause me many RE :( ](@praveen123 modify the problem statement)


Jumpy:
20140303 06:49:23
easy if you think simple and be aware of boundary conditions 

Akhilesh Anandh:
20140303 06:49:23
Agree with fitcat.. it gave me a runtime error 

fitcat:
20140303 06:49:23
@PS:


yashag:
20140303 06:49:23
My submission id is 11022017.


Sameer:
20140303 06:49:23
Don't use string in c++.. costed me 2 WA's :( :) 

Kevin Sebastian:
20140303 06:49:23
any tricky test cases? 
Added by:  praveen123 
Date:  20140203 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 