AMSGAME.txt

//https://www.codechef.com/problems/AMSGAME2
// author: Pravash Ranjan Nayak

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;

 /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package pkg21.days.of.code;

/**
 *
 * @author Pravash Ranjan
 */
 class dp1 {
     static class FastReader{BufferedReader br;StringTokenizer st;public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}String next(){ while (st == null || !st.hasMoreElements()){try{st = new StringTokenizer(br.readLine());}
        catch (IOException  e){e.printStackTrace();}}return st.nextToken();}int nextInt(){return Integer.parseInt(next());}long nextLong(){return Long.parseLong(next());} 
        double nextDouble(){return Double.parseDouble(next());}String nextLine(){String str = ""; try{str = br.readLine();}catch (IOException e){e.printStackTrace();}return str;}}
    public static void main(String args[])
    {
        FastReader ob=new FastReader();
        int t=ob.nextInt();
        while(t-->0)
        {
            int n =ob.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=ob.nextInt();
            long dp[][]=new long[70][10000+5];
            for(int i=0;i<70;i++)
            {
                for(int j=0;j<10000+5;j++)
                {
                    dp[i][j]=-1;
                }
            }
            long sum=0;
            for(int i=0;i<n;i++)
                sum+=recurse(i+1,n,a,a[i],dp);
            System.out.println(sum==-1?0:sum);
        }
            
    }
    public static int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
}
    public static long recurse(int pos,int N,int a[],int gd,long dp[][])
    {
        
        if(pos==N && gd==1)
            return 1;
        if(pos==N && gd!=1)
            return 0;
        if(dp[pos][gd]!=-1)
            return dp[pos][gd];
        return dp[pos][gd]=recurse(pos+1,N,a,gd,dp)+recurse(pos+1,N,a,gcd(gd,a[pos]),dp);
                
    }
    
}