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 ith 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 (105) 
-  0 ≤ A[i] ≤ 1000000 (106)

-----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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
t = int(input())

res = []
for i in range(t):
 n = int(input())
 arr = [int(i) for i in input().split()]
 
 num_2 = 0
 num = 0
 
 for j in range(len(arr)):
  if arr[j] == 2:
   num_2 += 1
   
  if arr[j] > 2:
   num += 1
   
 res.append(num_2 * num + (num * (num - 1)) // 2)
 
for z in res:
 print(z)

T = int(input())
ans = []

for _ in range(T):
 N = int(input())
 A = [int(i) for i in input().split()]

 C2 = 0
 C = 0
 for i in range(N):
  if(A[i]==2):
   C2 += 1
  if(A[i]>2):
   C += 1
 ans.append(C2*C + (C*(C - 1))//2)
for i in ans:
 print(i)


try:
 for i in range(int(input())):
  n=int(input())
  l=list(map(int,input().split()))
  k=[]
  for i in l:
   if i >1:
    k.append(i)
  two=k.count(2) 
  c2=len(k)-two
  print((two*c2) + c2*(c2-1)//2)
except:
 pass

for _ in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 c = t = 0
 for i in range(n):
  if a[i]==2:
   t+=1
   c+=1
  elif a[i]>1:
   c+=1
 print(int((c*(c-1)/2)-(t*(t-1)/2)))

from collections import defaultdict
for _ in range(int(input())):
 n = int(input())
 ls = [int(x) for x in input().split()]
 n-=ls.count(1)
 n-=ls.count(0)
 twos = ls.count(2)
 ans = n*(n-1)//2
 if twos>1:
  ans-=(twos-1)*twos//2
 print(ans)

from collections import defaultdict
for _ in range(int(input())):
 n = int(input())
 ls = [int(x) for x in input().split()]
 n-=(ls.count(1)+ls.count(0))
 twos = ls.count(2)
 rest = twos*(n-twos) + ((n-twos)*(n-twos-1) )// 2
 print(rest)

from collections import defaultdict
for _ in range(int(input())):
 n = int(input())
 ls = [int(x) for x in input().split()]
 twos = 0;rest = 0
 for i in range(n):
  if ls[i]==0 or ls[i]==1:
   continue
  elif ls[i]==2:
   twos+=1
  else:rest+=1
 ans = (twos*rest) + (rest*(rest-1))//2
 print(ans)

for _ in range(int(input())):
 n = int(input())
 A = list(map(int, input().split()))
 ans = ones = twos = 0
 for i in range(n):
  if A[i] == 1 or A[i] == 0:
   ones += 1
  elif A[i] == 2:
   twos += 1
 n = n - ones
 ct2 = 0
 if twos > 1:
  ct2 = twos
 ans = (n * (n-1) // 2) - (ct2 * (ct2-1) // 2)
 print(ans)

for _ in range(int(input())):
 n = int(input())
 A = list(map(int, input().split()))
 ans = ones = twos = 0
 for i in range(n):
  if A[i] == 1 or A[i] == 0:
   ones += 1
  elif A[i] == 2:
   twos += 1
 n = n - ones
 ct2 = 0
 if twos > 1:
  ct2 = twos
 ans = (n * (n-1) // 2) - (ct2 * (ct2-1) // 2)
 print(ans)

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 n-=l.count(0)
 p=l.count(2)
 k=l.count(1)
 n-=k
 ans=n*(n-1)//2
 if p>1:
  ans-=(p-1)*p//2
 print(ans)

for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 t=0
 m=0
 for i in range(n):
  if a[i]==2:t+=1
  if a[i]>2:m+=1
 print( t*m + (m*(m-1))//2 )

# cook your dish here
for _ in range(int(input())):
 N=int(input())
 arr=list(map(int,input().split()))
 x=0
 y=0
 for i in arr:
  if(i==2):
   x+=1
  if(i>2):
   y+=1
 print(x*y + (y*(y-1))//2)

# cook your dish here
for _ in range(int(input())):
 
 n = int(input())
 l = list(map(int,input().split()))
 
 c2=0
 c=0
 for i in l:
  
  if i==2:
   c2+=1
  if i>2:
   c+=1
   
    
 print(c2*c + (c*(c-1))//2)



# cook your dish here
for _ in range(int(input())):
 
 n = int(input())
 l = list(map(int,input().split()))
 
 c2=0
 c=0
 for i in l:
  
  if i==2:
   c2+=1
  if i>2:
   c+=1
   
    
 print(c2*c + (c*(c-1))//2)


import math
test = int(input())
for _ in range(test):
 n=int(input())
 array =list(map(int, input().split()))
 count = n- array.count(1) - array.count(0) - array.count(2)
 print(count*(count-1)//2 + array.count(2)*count)

for _ in range(int(input())):
 n=int(input())
 a=[int(i) for i in input().split()]
 n-=a.count(0)
 n-=a.count(1)
 p=a.count(2)
 n-=p
 print(((n*(n-1))//2)+p*n)

from bisect import *
from collections import *
from sys import stdin,stdout
from queue import *
from itertools import *
from heapq import *
from random import *
from statistics import *
from math import *
import operator
inn=stdin.readline
out=stdout.write
for i in range(int(inn())):
 n=int(inn())
 a=list(map(int,inn().split()))
 d=defaultdict(list)
 s=0
 for i in range(n):
  if a[i]==1 or a[i]==0 or a[i]==2:
   d[a[i]].append(i)
 for i in range(n):
  if a[i]==0 or a[i]==1:
   continue
  if a[i]==2:
   k=len(d[0])-bisect(d[0],i)
   k1=len(d[1])-bisect(d[1],i)
   k2=len(d[2])-bisect(d[2],i)
   s+=(n-i-1)-(k+k1+k2)
   continue
  k=len(d[0])-bisect(d[0],i)
  k1=len(d[1])-bisect(d[1],i)
  s+=(n-i-1)-(k+k1)
 print(s)
  


t=int(input())
for _ in range(t):
 n=int(input())
 list1=list(map(int,input().strip().split()))
 
 count1=0
 count2=0
 for val in list1:
  if val==0 or val==1:
   count1+=1
  elif val==2:
   count2+=1
 
 temp1=n-count1
 temp2=0
 if count2>=2:
  temp2=count2
 
 print((temp1*(temp1-1))//2-(temp2*(temp2-1))//2)
 
 


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 s=sum(1 for el in l if el>2)
 c=l.count(2)
 print(c*s+s*(s-1)//2)

# cook your dish here
for t in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 a,b=0,0
 for i in range(n):
  if l[i]>2:
   a+=1
  elif l[i]==2:
   b+=1
 print(int(((a*(a-1)/2)+a*b)))

# cook your dish here
def solve():
 n = int(input())
 l = list(map(int, input().split()))
 t_2 = 0
 tn_2 = 0
 for i in range(len(l)):
  if l[i] > 2:
   tn_2 += 1
  elif l[i] == 2:
   t_2 += 1
 ans = (tn_2 * (tn_2 - 1)) / 2
 ans += t_2 * tn_2
 print(int(ans))


def __starting_point():
 t = int(input())
 while t != 0:
  solve()
  t -= 1
__starting_point()

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 t_2=0
 tn_2=0
 for i in range(len(l)):
  if l[i]>2:
   tn_2+=1
  elif(l[i]==2):
   t_2+=1
 ans=(tn_2*(tn_2-1))/2
 ans+=t_2*tn_2
 print(int(ans)) 

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 t_2=0
 tn_2=0
 for i in range(len(l)):
  if l[i]>2:
   tn_2+=1
  elif(l[i]==2):
   t_2+=1
 ans=(tn_2*(tn_2-1))/2
 ans+=t_2*tn_2
 print(int(ans))