Một mảng các số nguyên được gọi là hoàn hảo nếu như mỗi phần tử của nó đều chia hết cho 4.

Cho một mảng ~a_1, a_2, ..., a_n~. Trong một bước, bạn có thể chọn bất cứ 2 phần tử nào của xâu và bỏ chúng ra khỏi xâu ban đầu sau đó thêm tổng của hai phần tử đó vào xâu. Hãy tính số bước tối thiểu như trên để có thể tạo ra một mảng hoàn hảo.

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào chứ T – số test. T test được miêu tả như sau:
• Dòng đầu tiên của mỗi test chứa một số nguyên n.
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n~.

Dữ liệu ra

• Ở mỗi test, in ra một Dòng chứa một số - số bước nhỏ nhất phải thực hiện để tạo ra một xâu hoàn hảo. Nếu không thể tạo ra một mảng hoàn hảo nào, hãy in ra -1.

Ràng buộc

• 1 ≤ T ≤ ~10^5~
• 1 ≤ n ≤ ~10^5~
• 1 ≤ Tổng của n sau mỗi test ≤ ~10^6~
• 0 ≤ ~a_i~ ≤ ~10^9~

Ví dụ

Input:

1 
7 
1 2 3 1 2 3 8

Output:

3