Chef is playing a game on a sequence of N positive integers, say A₁, A₂, ... A_N. The game is played as follows.

• If all the numbers are equal, the game ends.
• Otherwise
  • Select two numbers which are unequal
  • Subtract the smaller number from the larger number
  • Replace the larger number with the result from above

Chef has already figured out that the game always terminates. He also knows, for a given sequence of integers, the game will always terminate on the same value, no matter how the game is played. Chef wants you to simulate the game for him and tell him if the game terminates on 1.

In fact, there may be many such games. Given a sequence of integers Chef wants to know the number of sub-sequences of the given sequence, for which, playing the above game on the subsuquence will terminate on 1. A sub-sequence can be obtained from the original sequence by deleting 0 or more integers from the original sequence. See the explanation section for clarity.

Input

The first line of the input contains an integer T, the number of test cases. Then follow the description of T test cases. The first line of each test case contains a single integer N, the length of the sequence. The second line contains N positive integers, each separated by a single space.

Output

For each test case, output a single integer - the number of sub-sequences of the original sequence, such that, playing the game on the sub-sequence results in ending the game with all the values equal to 1.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 60
1 ≤ A_i ≤ 10⁴
All A_i will be distinct.

Sample

Input
3
4
2 3 5 7
4
3 4 8 16
3
6 10 15

Output
11
7
1

Explanation

Test Case 1: The following 11 sub-sequences are counted.

• { 2, 3 }
• { 2, 5 }
• { 2, 7 }
• { 3, 5 }
• { 3, 7 }
• { 5, 7 }
• { 2, 3, 5 }
• { 2, 3, 7 }
• { 2, 5, 7 }
• { 3, 5, 7 }
• { 2, 3, 5, 7 }

Test Case 2: The following 7 sub-sequences are counted.

• { 3, 4 }
• { 3, 8 }
• { 3, 16 }
• { 3, 4, 8 }
• { 3, 4, 16 }
• { 3, 8, 16 }
• { 3, 4, 8, 16 }

Test Case 3: There are 8 subsequences of { 6, 10, 15 }

• {} => The game cannot be played on this sub-sequence
• { 6 } => The game cannot be played on this sub-sequence
• { 10 } => The game cannot be played on this sub-sequence
• { 15 } => The game cannot be played on this sub-sequence
• { 6, 10 } => The game cannot end at { 1, 1 }
• { 6, 15 } => The game cannot end at { 1, 1 }
• { 10, 15 } => The game cannot end at { 1, 1 }
• { 6, 10, 15 } => The game ends at { 1, 1, 1 }. Hence this is the only sub-sequence that is counted in the result.

 As we know problems in Dynamic programming requires a little look up in the constraints so we can say that  for every n we can visit it with maximum 10^4 values as after that values are bound to repeat

So a normal brute force of pick or leave would look like

            ret+=solve(curpos+1,lastgcd)
             ret+=solve(curpos+1,gcd(lastpos,arr[curpos])

To speed up this solution we memoise it as dp[position][gcd]  n is visited with that gcd again
we simply return the value in it.


       ******* code goes here *****************


#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
int arr[10010];
ll dp[70][10010];
int n;
using namespace std;
ll solve(int pos,int gcd)
{
         if(pos==n)
         {
                  return (gcd==1);
         }
         ll ans=0;
         if(dp[pos][gcd]!=-1)
         return dp[pos][gcd];
         int new_gcd=__gcd(gcd,arr[pos]);
         ans+=solve(pos+1,new_gcd);
         ans+=solve(pos+1,gcd);
         dp[pos][gcd]=ans;
         return dp[pos][gcd];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    //      int n;
          cin>>n;
          for(int i=0;i<n;i++)
          {
                scanf("%d",&arr[i]);
          }
          for(int i=0;i<=63;i++)
          {
               for(int j=0;j<=10005;j++)
               dp[i][j]=-1;
          }
          ll ans=0;
          ans=solve(0,0);
          cout<<ans<<endl;
    }
    return 0;
}