Hacky is a genius cat. He is given two strings of digits(hac1,hac2) and his job is to find the Cardinal of the two strings. Cardinal is defined as the length of the longest substring of digits in hac1 such that there is a substring of the same length in hac2 which satisfies the following constraint. Each digit in the substring of hac2 is the exact integer multiple of the corresponding digit in the substring of hac1. Thus, "24" is a multiple (2) of "12", but "72" is not a multiple of "36".
Multiplication factors from 0 to 9 are possible.
First line of input contains T,the number of test cases. Each case contains two strings hac1 and hac2.
Print the Cardinal(the length of the longest substring with a multiple).
- Leading zeros can be present in hac1 and hac2 and all substrings.
- Each digit multiple must be exactly a single digit. eg: '2' x 8 does not match but '2' x 4 does.
- Input Strings will have between 1 and 50 characters inclusive.
- Each character of the strings will be between '0' and '9' inclusive.
- T is less than 50.
In the first test case, 333221*2=666442 (multiple 2), hence the cardinal is 6.
Problem Setter: Anjali Singh