313 : スライドパズル

スライドパズルでは, カウンタを空白のスペースに向けて横または縦へスライドさせることができる. ゲームの目的は, 赤のカウンタを盤の左上角から右下角へ動かすことである；スペースはつねに右下角にある状態から始まる. 例えば次の一連の図は, $2×2$の盤にて5手でゲームを完了させる様子を示している.

p_313_sliding_game_1.gif

$S(m,n)$を,$m×n$の盤でゲームを完了させる最小の手数を表すとする. 例えば,$S(5,4) = 25$であることが確かめられる.

$100$未満の素数$p$について,$S(m,n)=p^2$となる盤はちょうど 5482 個ある.

$10^6$未満の素数 p について,$S(m,n)=p^2$となる盤は何個あるか.