在滑动游戏中，计数器可以水平或垂直滑入空白区域。游戏的目标是将红色计数器从网格的左上角移动到右下角；空间总是从右下角开始。例如，以下图片序列显示了如何在 $2$ x $2$ 网格上通过五步完成游戏。

令 $S(m,n)$ 表示在 $m$ x $n$ 网格上完成游戏的最小步数。例如可以验证$S(5,4)=25$。

总共有 $5482$ 个网格，其中 $S(m,n)=p^2$，其中 $p<100$ 是质数。

$S(m,n)=p^2$ 有多少个网格，其中 $p<{10}^6$ 是质数？