All Submissions


Problem Statement

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.


INPUT

First line of input contains T,the number of test cases. Each case contains two strings hac1 and hac2.

Output

Print the Cardinal(the length of the longest substring with a multiple).

Constraints
  • 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.

Sample Input


5
876533322142 11111166644202345
123452130 569777639065
11111111111 11111111111
45678903456 00000000000
2345 1234


SAMPLE OUTPUT


6
4
11
11
3


EXPLAINATION

In the first test case, 333221*2=666442 (multiple 2), hence the cardinal is 6.

Problem Setter: Anjali Singh

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 50 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0