又是一個序列問題
wcwu 自從考上大學之後開始荒廢競程,導致他連最簡單的 Hello World! 都寫不出來了!今天他聰明的隊友 Aestivate 遇到了一個序列問題,思索許久之後決定拿來詢問 wcwu,但是 wcwu 早就不會寫程式了!所以他只好把這個問題委託給你,請問你有辦法幫 wcwu 想出這題的答案嗎? (此題為真人真事改編)
有一個長度為 \(n\) 的數列 \(v\),Aestivate 要從數列中選取兩個子序列 \(a=\{ v_{x_1}, v_{x_2},...,v_{x_p} \}\) 和 \(b=\{ v_{y_1}, v_{y_2},...,v_{y_q} \}\) (\(1\leq x_1< x_2< ... < x_p\leq n\), \(1\leq y_1< y_2< ... < y_q\leq n\)),滿足下列三個規則:
對所有 \(1\leq i\leq p\) 和 \(1\leq j\leq q\),都有 \(x_i\neq y_j\)。
對所有 \(2\leq k\leq p\),都有 \(v_{x_{k-1}} \equiv v_{x_k}\pmod{10}\) 或 \(v_{x_{k-1}}+v_{x_k}\) 為質數。
對所有 \(2\leq l\leq q\),都有 \(v_{y_{l-1}} \equiv v_{y_l}\pmod{10}\) 或 \(v_{y_{l-1}}+v_{y_l}\) 為質數。
請求最大的 \(p+q\) 值為何?
註:關於子序列的定義,可以參考 https://en.wikipedia.org/wiki/Subsequence
Input
第一行包含一個正整數 \(T\),代表測資的筆數。
對於每一筆測資,第一行包含一個正整數 \(n\),代表陣列 \(v\) 的長度。
第二行包含 \(n\) 個正整數 \(v_i\),\(1\leq i\leq n\)。
\(1\leq T\leq 5000\), \(2\leq \Sigma n\leq 10000\), \(1\leq v_i\leq 50\)
Output
輸出 \(T\) 行,其中第 \(i\) 行代表第 \(i\) 筆測資最大的 \(p+q\) 值。
Constraints
第 \(1\) 組測資,必有 \(v_i=1\) 或 \(v_i=3\)。 (\(4 \%\))
第 \(2\) 組測資,\(1\leq T\leq 500\), \(2\leq \Sigma n\leq 1000\) (\(48 \%\))
第 \(3\) 組測資,無特別限制 (\(48 \%\))
Sample Input 1
4
3
1 4 3
2
11 9
5
1 1 1 1 1
6
10 20 30 47 2 1
Sample Output 1
3
2
5
5
Comments