#include
using namespace std;
int main()
{
long long int T,N,W,n,m,ans;
cin>>T;
if(T>=1&&T<=10)
{
while(T>0)
{
n=m=0;
ans=0;
cin>>N;
if(N>=2&&N<=100000)
{
while(N>0)
{
cin>>W;
if(W>=0&&W<=1000000)
{
if(W==2)
{
n++;
}
if(W>2)
{
m++;
}
N--;
}
}
if(m==1)
{
ans=n*m;
}
else if(m==2)
{
ans=m*n+1;
}
else if(m>2)
{
ans=m*n;
long long int a,b;
a=1;
n=m;
while(n>0)
{
a*=n;
n--;
}
b=1;
n=m-2;
while(n>0)
{
b*=n;
n--;
}
b=b*2;
while(a>0)
{
a-=b;
ans+=1;
}
}
cout<<endl<<ans;
}
T--;
}
}
}