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 vị 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ụ 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:

Dòng đầu tiên của đầu vào chứa một số nguyên ~q (1 \le q \le 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 \le n \le 10^5)~.
• Dòng ~2~: Chứa ~n~ số nguyên ~a[1], a[2], ..., a[n] (1 \le a[i] \le 10^9, 1 \le i \le n)~.

Kết quả:

• Ghi 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 \le n \le 10^2, 1 \le a[i] \le 10~.
• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài với ~1 \le n \le 10^5, 1 \le a[i] \le 10^9~.

  Ví dụ:

Sample Input

2
5 
2 4 5 3 1
4
5 4 1 3

Sample Output

3
2

Giải thích:

Trong test 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~.