## Problem: Possible groups

Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three only, the group should be such that the sum of all elements in that group is a multiple of 3. Count all possible number of groups that can be generated in this way.

Input: arr[] = {3, 6, 7, 2, 9} Output: 8 Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3, 6,9}, {3, 7, 2}, {7, 2, 6}, {7, 2, 9}

**Input:**

The first line of input contains an integer T denoting the number of test cases.

The first line of each test case is N, where N is the size of array.

The second line of each test case contains N elements of input array.

**Output:**

Print number of all possible group.

**Constraints:**

1 ≤ T ≤ 50

1 ≤ N ≤ 80

1 ≤ arr[i] ≤ 100

**Example:**

Input

2

5

3 6 7 2 9

4

2 1 3 4

Output

8

4

Implementation: Python 2.7

from itertools import * def possible_groups(l): groups_2 = [x for x in list(combinations(l, 2)) if sum(x)%3==0] groups_3 = [x for x in list(combinations(l, 3)) if sum(x)%3==0] return len(groups_2) + len(groups_3) if __name__ == '__main__': t = input() for _ in range(t): n = input() l = map(int, raw_input().split()) print possible_groups(l)

## Reply