폴리오미노 거듭제곱

폴리오미노(polyomino)는 단위 정사각형을 기본 조각으로 하는 도형이다. 정사각형 격자 위 서로 다른 위치에 놓인, 하나 이상의 동일한 정사각형을 이어 붙여 만든 연결된 도형이며, 모든 정사각형이 변을 공유하는 연결을 따라 서로 이어져 있어야 한다(꼭짓점만 맞닿는 연결은 허용되지 않는다). 가장 잘 알려진 폴리오미노로는 정사각형 네 개로 이루어진 일곱 가지 테트로미노(테트리스로 유명하다)와 정사각형 두 개로 이루어진 도미노가 있다.

어떤 폴리오미노는 더 작은 하나의 폴리오미노를 여러 개 복사한 뒤, 회전이나 대칭 없이 평행이동만으로 평면의 서로 다른 위치에 붙여서 만들 수 있다. 이렇게 만들 수 있는 폴리오미노를 그 작은 폴리오미노의 거듭제곱(power)이라고 부른다. 정확히 말하면, 어떤 폴리오미노를 더 작은 폴리오미노의 평행이동 복사본 $k$개로 겹치지 않게 빈틈없이 덮을 수 있으면 그 폴리오미노를 $k$-거듭제곱이라고 한다.

첫째 줄에 두 양의 정수 $h$와 $w$가 주어진다 ($h, w \le 10$).

이어지는 $h$개의 줄에는 각각 $w$개의 문자가 주어져 $h \times w$ 격자를 이룬다. 각 문자는 . 또는 X이며, X는 폴리오미노에 속하는 칸을, .은 빈칸을 나타낸다. X로 표시된 칸들은 하나의 폴리오미노를 이룬다(변으로 연결되어 있다).

$2 \le k \le 5$를 만족하는 정수 $k$ 중에서, 주어진 폴리오미노가 $k$-거듭제곱이 되는 가장 작은 $k$를 한 줄에 출력한다. 즉, 더 작은 하나의 폴리오미노의 평행이동 복사본으로 이 폴리오미노를 빈틈없이 덮을 때 필요한 복사본 개수의 최솟값을 출력한다. 그러한 $k$가 존재하지 않으면 No solution을 출력한다.