Update appNew update is available. Click here to update.

Stamp Box

Last Updated: 17 Apr, 2021
Difficulty: Moderate


Try Problem

Ninja got a moody friend who is very curious about colors. His friend presented him with a design made of various colors and gave him a stamp box. The various colors are given in the form of numbers. He can adjust the dimensions of the stamp box as per need.

Ninja is supposed to draw the given design under the given conditions:

1. Ninja can use one color at a time.
2. Ninja can’t use one color more than once.
3. The stamp box is in the form of a rectangle. So, Ninja can only draw rectangles(or squares) by adjusting the dimensions of the stamp box.
4. Once Ninja prints any color using the stamp box, the old color won’t be visible and only the new color will be visible.

Ninja is very busy in doing some other stuff but he can find some time if it is possible to print the design under the given conditions and if it is impossible to print the design, he won’t waste time on it.

Can you help Ninja to find if it is possible to print the design or not?

Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains two space-separated integers ‘N’ and ‘M’, which denotes the number of rows and columns in the matrix ‘MAT’.

The next ‘N’ lines contain ‘M’ space-separated integers denoting the colors at that point.
Output Format:
For each test case, print 1 if it is possible to draw the given design. Otherwise, print 0.

Print the output of each test case in a separate line.
You are not required to print the expected output, it has already been taken care of. Just implement the function.
1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
1 <= MAT[i][j] <= 50

Where 'MAT[i][j]' is the color in the coordinate (i, j).

Time Limit: 1 sec