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. 對所有 \(1\leq i\leq p\) 和 \(1\leq j\leq q\)，都有 \(x_i\neq y_j\)。

2. 對所有 \(2\leq k\leq p\)，都有 \(v_{x_{k-1}} \equiv v_{x_k}\pmod{10}\) 或 \(v_{x_{k-1}}+v_{x_k}\) 為質數。

3. 對所有 \(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