People curse Garg for always having Suffix Array in his problem set.
Having thought upon this for some time, he decided that he will not have this topic again this time.
But as his love for STRINGS never actually ceases to exist, he decided once again to play with strings.
He provides you two strings X and Y.
You need to divide both strings into K parts as per the following rules-
K should be as small as possible.
Since Garg has to make output files as soon as possible in order to meet his girlfriend, help him by providing the minimum valid value of K.
The first line of the input contains an integer T - denoting the number of the test cases.
Each test case will be consisting of two lines containing string X and Y respectively .
For each test case, an integer which will denote the value of K is output on a separate line.
1<=|X|,|Y|<=80, where |X| and |Y| denote lengths of X and Y respectively.
X and Y comprise only lower case characters
Problem Setter:- Shivam Garg
In the first case -
X1 = a , X2 = b , X3 = c , X4 = NULL
Y1 = NULL , Y2 = NULL , Y3 = NULL , Y4 = D
In the second case -
X1 = ab , X2 = xy
Y1 = ba , Y2 = yx