Game of 3 Problem Statement

Help the Ultimate Ninja Ankush form groups of integers such that the sum of each group is divisible by 3. Given an array of integers, count how many groups of sizes 2 and 3 can be created where the sum of the group elements is a multiple of 3.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer, ‘N,’ specifying the number of elements in the array.
The second line of each test case contains ‘N’ space-separated integers, representing the array elements.

Output:

For each test case, return an integer denoting the total number of groups that can be formed.

Example:

Input:
N = 5, ARR = [1, 2, 3, 4, 5]
Output:
8

Explanation:

The valid pairs are: (1,3), (1,2), (1,5), (2,4), (4,5), (1,2,3), (3,4,5), and (1,3,5).

Constraints:

• 1 <= ‘T’ <= 10
• 1 <= ‘N’ <= 5000
• 0 <= ‘ARR[i]’ <= 10⁴
• Time Limit: 1 sec

Note:

Focus on implementing the function returning the expected result as outputs are pre-handled.