令 $n$ 为正整数。假设坐标 $(x,y)=(2^{i}modn,3^{i}modn)$ 处有 $0\le i\le 2n$ 的站点。我们将把坐标相同的站点视为同一站点。

我们希望形成一条从 $(0,0)$ 到 $(n,n)$ 的路径，使得 $x$ 和 $y$ 坐标永远不会减少。
令 $S(n)$ 为该路径可以通过的最大站数。

例如，如果$n=22$，则有$11$个不同站点，有效路径最多可以经过$5$个站点。因此，$S(22)=5$。 下面以最佳路径为例说明该情况：

还可以验证 $S(123)=14$ 和 $S(10000)=48$。

求 $\sum S(k^5)$ 为 $1\le k\le 30$。