Cho một dãy gồm n số nguyên a[1], a[2], …, 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 bị trí bất kì trong dãy)

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

Nhiệm vụ cuả 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.

Input:

• Dòng đầu tiên của Input chứa một số nguyên q (1 ≤ q ≤ 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 ≤ n ≤ 10⁵)
• Dòng 2: chứa n số nguyên a[1], a[2], …, a[N] (1 ≤ a[i] ≤ 10⁹, 1 ≤ i ≤ n).

Output:

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.

Hạn chế:

• Có 60% số test ứng với 60% số điểm của bài với 1 ≤ n ≤ 10², 1 ≤ a[i] ≤ 10
• Có 40% số test ứng với 40% số điểm của bài với 1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ 10⁹

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