Minimum Perfect Square in a Matrix

You are given a rectangular matrix consisting of integers. Your task is to find the smallest positive integer in the matrix that is a perfect square.

A number \(x\) is a perfect square if there exists an integer \(y\) such that \(y^2 = x\) and \(x > 0\). If no such number exists in the matrix, output \(-1\).

Read the input from standard input and produce the output to standard output.

inputFormat

The input begins with an integer (T) representing the number of test cases. For each test case, the first line contains two space-separated integers (R) and (C), representing the number of rows and columns in the matrix. This is followed by (R) lines, each containing (C) space-separated integers, which are the elements of the matrix.

outputFormat

For each test case, output a single integer — the smallest positive perfect square in the matrix, or (-1) if no perfect square exists.## sample

1
3 3
10 4 5
3 16 2
8 1 7

1