1037 . 2025C班第一階段階段考_pE
Description
質數判斷
小橘是個數字控，他最近寫了一個程式，會不斷地產生質數，然後把它們接在一起存成一個長長的數字記錄下來。
但有一天他發現：他忘記把質數之間的分隔記下來了！
現在他只剩下一整串長度為 $|S_i| $ 的數字，完全不知道當初是怎麼切的了。
請你幫忙找出，有多少種切法可以把這串數字分割成一段段都是質數的子字串。
合法切法中每個子字串都應為非空的字串，可以有前導 $0$。
Input Format
每筆測資有多個輸入
第一行為一個數字 $t$, $t \le 20$，代表接下來有 $t$ 個字串
接下來的 $t$ 行各有一個數字字串 $S_i$，$1 \le |S_i| \le 18$
Output Format
輸出 $t$ 行，第 $i$ 行為 $S_i$ 的合法切法數
Sample Input 1
4
615
17372
2914
303
615
17372
2914
303
Sample Output 1
1
3
0
1
3
0
1
Hints
上課教的質數判斷應該有機會在 subtask 3 吃 TLE，可以查查看有什麼方法可以讓它變快，也許會跟數字 6 有關？
範例測資說明：
615 可以被切成
61 | 5
17372 可以被切成
17 | 3 | 7 | 2
17 | 37 | 2
173 | 7 | 2
2914 沒有辦法切成數個質數
303 可以被切成
3 | 03
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $1 \le |S_i| \le 6$ | 25 |
| 2 | 5~9 | $1 \le |S_i| \le 12$ | 25 |
| 3 | 10~19 | 無其他特殊限制 | 50 |