from itertools import permutations as p
import numpy as np
def gcd(a,b): 
    # Everything divides 0  
    if (a == 0): 
        return b 
    if (b == 0):
        return a 
    # base case 
    if (a == b): 
        return a 
    # a is greater 
    if (a > b): 
        return gcd(a-b, b)    
    return gcd(a, b-a) 
n=int(input())
man=[]
list5=[]
for i in range(0,n):
    list2=[]
    w=int(input())
    list1=input().split()
    go="".join(list1)
    list2=list(p(go,w))
    print(list2)
    count=0
    final=[]
    for k in list2:
        k=list(k)
        for p in range(1,len(k)):
            e=k[0:p]
            f=k[p:]
            e=[int(i) for i in e]
            f=[int(i) for i in f]
            e=sorted(e)
            f=sorted(f)
            e=[str(i) for i in e]
            f=[str(i) for i in f]
            a1="".join(e)
            a2="".join(f)
            e=[int(i) for i in e]
            f=[int(i) for i in f]
            y=np.prod(e)
            z=np.prod(f)
            t=gcd(y,z)
            st=a1+','+a2
            if (st not in final) and (t==1):
                final.append(st)
                count=count+1    
                
    print(count)           

static int solve(int [] a) 
    {
        DisjointSet<Integer> ds=new DisjointSet<Integer>();
        HashSet<Integer> set=new HashSet<Integer>();
        int count1=0;
        for(int i:a)
             {
                set.add(i);
                ds.makeSet(i);
                if(i==1)
                    count1++;
                
             }
        Iterator <Integer> i=set.iterator();
        while(i.hasNext())
        {
            int x=i.next();
            if(x==1)
                continue;
            else
            {
                Iterator<Integer> j=set.iterator();
                while(j.hasNext())
                {
                    int y=j.next();
                    if(y!=x && gcd(x,y)!=1)
                            ds.union(x,y);
                }
            }       
        }   
        int count=ds.numberOfSets()+(count1!=0?count1-1:0);
        return (int)((power(2,count,1000000007)-2+1000000007)%1000000007);
    }