Subtraction Game 2

All submissions for this problem are available.
Chef is playing a game on a sequence of N positive integers, say A_{1}, A_{2}, ... 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 subsequences of the given sequence, for which, playing the above game on the subsuquence will terminate on 1. A subsequence 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 subsequences of the original sequence, such that, playing the game on the subsequence results in ending the game with all the values equal to 1.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 60
1 ≤ A_{i} ≤ 10^{4}
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 subsequences 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 subsequences 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 subsequence
 { 6 } => The game cannot be played on this subsequence
 { 10 } => The game cannot be played on this subsequence
 { 15 } => The game cannot be played on this subsequence
 { 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 subsequence that is counted in the result.
Author:  satej 
Tester:  gamabunta 
Editorial  https://discuss.codechef.com/problems/AMSGAME2 
Tags  cook34, dynamicprogramming, satej , simple 
Date Added:  11052013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions