Little chef has just been introduced to the world of numbers! While experimenting with addition and multiplication operations, the little chef came up with the following problem:

Given an array A of non-negative integers, how many pairs of indices i and j exist such that A[i]*A[j] > A[i]+A[j] where i < j .
Now being a learner, little chef isn't able to solve this problem efficiently and hence turns to you for help.

Input
First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of integers in the array. The next line contains N space separated integers where the i^th integer represents A[i].
Note : There may be trailing spaces on each line of input.

Output
For each test, print the required number of pairs in a single line.

Constraints

1 ≤ T ≤ 10
2 ≤ N ≤ 100000 (10^5)
0 ≤ A[i] ≤ 1000000 (10^6)

Example
Input:
2
3
3 4 5
4
1 1 1 1

Output:
3
0

Explanation
Example case 1.
All pairs of numbers satisfy the criteria. Total number of pairs equals 3.

Example case 2.
No pair of numbers satisfy the criteria.

见题面

见题面