#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        // dp[i][j] là số cặp tối đa có thể tạo từ i phần tử đầu tiên để lại j phần tử (0 hoặc 1)
        // j là số lượng phần tử chưa ghép (số dư mod 3)
        // Tuy nhiên, do chỉ quan tâm đến số cặp chia hết 3, ta có thể tối ưu state
        // State: dp[i][r] = số cặp tối đa từ i phần tử, với r phần tử chưa ghép?
        // Hoặc đơn giản hơn: đếm số lượng các số theo số dư mod 3.
        // Approach này thực ra là đếm trực tiếp thay vì DP.

        // Tính tổng các chữ số modulo 3 cho từng số
        long long cnt[3] = {0, 0, 0};
        for (int x : a) {
            int s = 0;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            cnt[s % 3]++;
        }

        // Các cặp có tổng chia hết cho 3:
        // 1. (0, 0) -> tổng chia hết 3
        // 2. (1, 2) -> tổng chia hết 3
        // 3. (0, 1) hoặc (0, 2) -> không chia hết
        // 4. (1, 1) -> tổng chia hết 2
        // 5. (2, 2) -> tổng chia hết 1

        // Đếm số cặp (0, 0)
        long long pairs_0 = cnt[0] / 2;
        // Đếm số cặp (1, 2)
        long long pairs_12 = min(cnt[1], cnt[2]);

        cout << pairs_0 + pairs_12 << "\n";
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        long long cnt[3] = {0, 0, 0};
        for (int i = 0; i < n; i++) {
            long long x;
            cin >> x;
            // Tính tổng các chữ số
            long long sum_digits = 0;
            while (x > 0) {
                sum_digits += x % 10;
                x /= 10;
            }
            cnt[sum_digits % 3]++;
        }

        // Phép toán tham lam:
        // 1. Luôn ghép các cặp (0, 0) trước, mỗi cặp tốn 2 số dư 0.
        // 2. Luôn ghép các cặp (1, 2) trước, mỗi cặp tốn 1 số dư 1 và 1 số dư 2.
        // Đây là lựa chọn tối ưu vì nó không ảnh hưởng đến các cặp còn lại.

        long long res = (cnt[0] / 2) + min(cnt[1], cnt[2]);
        cout << res << "\n";
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        // Khai báo mảng đếm 3 phần tử cho 3 loại
        int count_mod[3] = {0, 0, 0};

        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;

            // Tính tổng các chữ số của số đó
            int sum = 0;
            int temp = num;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }

            // Đếm số lượng theo phần dư khi chia 3
            count_mod[sum % 3]++;
        }

        // Tính toán số cặp
        // Cặp (0,0): có count_mod[0] / 2 cặp
        // Cặp (1,2): có min(count_mod[1], count_mod[2]) cặp

        int ans = count_mod[0] / 2 + min(count_mod[1], count_mod[2]);
        cout << ans << endl;
    }
    return 0;
}