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)