제곱수 찾기

N행 M열 크기의 표 A가 있고, 각 칸에는 한 자리 숫자가 하나씩 적혀 있다.

연두는 서로 다른 칸을 1개 이상 고르려고 한다. 단, 고른 순서대로 나열했을 때 칸들의 행 번호가 등차수열을 이루어야 하고, 열 번호도 등차수열을 이루어야 한다. 이렇게 고른 칸에 적힌 숫자를 고른 순서대로 이어 붙이면 하나의 정수가 만들어진다.

연두가 만들 수 있는 정수 중에서 가장 큰 완전제곱수를 구하여라. 완전제곱수란 어떤 정수를 제곱하여 얻을 수 있는 수이다.

첫째 줄에 두 정수 N과 M이 공백으로 구분되어 주어진다.

이어지는 N개의 줄에는 표의 각 행이 1번 행부터 N번 행까지 순서대로 주어진다. 각 줄에는 그 행의 1번 열부터 M번 열까지의 숫자가 공백 없이 이어져 있다.

연두가 만들 수 있는 가장 큰 완전제곱수를 첫째 줄에 출력한다. 완전제곱수를 하나도 만들 수 없으면 -1을 출력한다.

• 1 ≤ N, M ≤ 9
• 표의 각 칸에 적힌 숫자는 0 이상 9 이하이다.