Problem7316--CodeChef AMSGAME2 - Subtraction Game 2

7316: CodeChef AMSGAME2 - Subtraction Game 2

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

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 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 00 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 \le N \le 60$
$1 \le A_i \le 10^4$
All $A_i$ will be distinct.

Sample 1 Input 

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

Sample 1 Output 

11
7
1
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.

HINT

难度系数：2105
题目来源：CodeChef AMSGAME2

Source/Category

 
Submit