402590: GYM100814 E Palmyra

Palmyra is an oasis in the Syrian desert, north-east of Damascus, Palmyra contains the monumental ruins of a great city that was one of the most important cultural centers of the ancient world.

Omar is a famous Archaeologist from Egypt, he came to Syria in a monument drilling mission.

After one year of hard work with his team, Omar has a very good reason to believe that the ancient Syrians used the base - 6 numerical system (instead of the base - 10 we usually use). They found an ancient map, and they plan to use it to support their claim.

The map describes a rectangular city buried underground, the city has n × m district distributed on n rows and m columns. Each district contains a magical stone has a power p. If we merge two stones of power a and b we will have a stone of power a × b. Omar will dig exactly n + m - 1 districts starting from the most top left district, each time he digs a district he can choose to move either right or down.

Omar thinks that, after moving in the described way and merging all the magical stones he has, he will get a stone with some trailing zeros in the base - 6 representation of its power.

Given the power of stones in each district , Your task is to tell Omar what is the maximum possible number of trailing zeros in the base - 6 numeral system representation of the power of the final stone he could make.

Your program will be tested on one or more test cases. The first line of the input contains a single integer T the number of test cases. Followed by T test cases.

Each test case consists of N+1 lines. The first line contains two integers N (2  ≤  N  ≤  100), M (2  ≤  M  ≤  100), the dimensions of the city.

The next N lines consists of M integers separated by a single space: X_ij (1  ≤  X_ij  ≤  10³) which refers to the power of the stone in the j^th district of the i^th row written in base - 10 numeral system representation.

For each test case print a single line containing the maximum possible number of trailing zeros in the base - 6 representation of the final merged stone power.

1
3 3
3 2 3
2 3 2
3 2 3

2

Trailing zeros are a sequence of continuous 0's in the right most digits of the representation of a number, that are followed by a none-zero digit, for example: 180₁₀ = 500₆ has one trailing zero in the decimal representation, and two trailing zeros in base-6 system.