Cho một dãy gồm \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\). Trong một thao tác, bạn có thể chọn hai phần tử của dãy và thay thế chúng bằng phần tử tổng của chúng (bạn có thể chèn phần tử tổng này vào vị trí bất kỳ trong dãy).

Ví dụ: từ mảng \(a\ = \ \lbrack 5,1,4\rbrack\), bạn có thể tạo ra các dãy sau: \(\lbrack 6,\ 4\rbrack,\ \lbrack 1,\ 9\rbrack\) và \(\lbrack 5,\ 5\rbrack\) bằng thao tác nói trên.

Nhiệm vụ của bạn là tìm số phần tử tối đa có thể chia hết cho 5 trong mảng kết quả sau khi thực hiện một số lần tùy ý thao tác nói trên (có thể là 0 lần).

Bạn phải trả lời \(q\) truy vấn độc lập.

Dữ liệu vào:

Dòng đầu tiên của đầu vào chứa một số nguyên \(q\ (1\ \leq \ q\ \leq \ 100)\) là số truy vấn. Tiếp theo là mô tả \(q\) truy vấn, mỗi truy vấn gồm 2 dòng:

+ Dòng 1: chứa một số nguyên \(n\ (1\ \leq \ n\ \leq \ 10^{5})\).

+ Dòng 2: chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\) \((1 \leq a_{i} \leq 10^{9},\ 1 \leq i\ \leq \ n)\).

Kết quả:

Chương trình của bạn cần in ra \(q\) dòng, dòng thứ \(i\) ghi kết quả của truy vấn thứ \(i\), là một số nguyên cho biết số phần tử tối đa chia hết cho 5 trong mảng kết quả sau khi thực hiện một số lần tùy ý thao tác được mô tả trong đề bài.

Ràng buộc:

+ Có 60% số test ứng với 60% số điểm của bài với \(1 \leq n \leq 10^{2},\ 1 \leq a_{i} \leq 10\).

+ Có 40% số test ứng với 40% số điểm của bài với\(\ 1 \leq n \leq 10^{5},\ 1 \leq a\_ i \leq 10^{9}\).

Ví dụ:

Giải thích ví dụ: Có 2 truy vấn

Truy vấn 1: \(n\ = \ 5\), mảng ban đầu là \((2,\ 4,\ 5,\ 3,\ 1)\), thu gọn mảng để tăng số phần tử chia hết cho 5 bằng 2 thao tác cộng: 2+3, 4+1, ta được mảng 3 phần tử (5, 5, 5), mảng kết quả có 3 phần tử chia hết cho 5. Đáp án là 3.

Truy vấn 2: \(n\ = \ 4\), mảng ban đầu là \((5,\ 4,\ 1,\ 3)\), thu gọn mảng bằng 1 thao tác cộng: 4+1 ta được mảng 3 phần tử \((5,\ 5,\ 3)\), mảng kết quả có 2 phần tử chia hết cho 5. Đáp án là 2.