При игре в пятнашки фишку можно перемещать в свободное поле горизонтально или вертикально. Цель игры - переместить красную фишку из верхнего левого угла сетки в нижний правый угол; во время начала игры пуст всегда нижний правый угол. К примеру, следующая последовательность картинок показывает, как можно пройти игру в 5 ходов на клетке 2 на 2.

Пусть S(m,n) представляет собой минимальное число ходов, которыми можно пройти игру на сетке размерами m на n. К примеру, можно убедиться, что S(5,4) = 25.

Существует ровно 5482 сеток, для которых S(m,n) = p², где p < 100 является простым числом.

Сколько сеток можно получить, для которых S(m,n) = p², где p < 10⁶ является простым числом?