Jennifer is a brilliant potion makers at Hogwarts and is a close friend of Harry Potter. Harry has to open the Chamber of Secrets but the door can only be destroyed by a particular combination of ingredients. Draco, Harry's sworn enemy will do anything in his power to stop the opening of the Chamber.
Each ingredient is denoted by a power p. When an ingredient is added to the solution, power of the solution becomes the sum of the power of two most recent ingredients added. The power of the solution can be cancelled if somebody adds an ingredient to the current solution whose power is less than the solution's current power and divides the solution's power completely.
Given a set of n ingredients, Jennifer makes a final solution, adding one ingredient at a time to the solution such that Draco is not able to cancel the solution at any point of time. Remember Draco has infinite access to ingredients of all power i.e. power ranging from 2 to 100000.
Your task is to calculate the number of sequences possible in which Jennifer can make the final solution.
Note :
1. When first ingredient is added the power of solution is equal to the power of first ingredient.
2. update Draco can add ingredient to solution once Jennifer is finish with all the ingredient.

Input :
First line contains the number of test cases, t. Each test case contains a single integer ‘n’ in the first line and in second line there are n space separated integer each representing power p of ingredient i.

Output :
Each row contains number of possible sequences for corresponding set of ingredients

Constraints :
1<=t<=10
1<=n<=10
2<=p<=100000