You have been given an array consisting of n integers, \((a_1, a_2,...a_n)\). You can perform the following operations:

• In each move, you can partition the array into two non-empty contiguous parts, such that the sum of divisors of the elements in the left part is equal to that of the rigth part.
  Formally:
  let the array be divided into 2 parts such that we have \((a_1, a_2,...a_k)\) and \((a_{k+1}, a_{k+2},...a_n)\). Then,
  \(\sum_{i=1}^{k}f(a_i) = \sum_{i=k+1}^{n}f(a_j)\), where f(x) = number of divisors of x.
• You get 1 point if making a move is possible, otherwise the game ends.
• After each move you can discard one of the partition and continue with the other.

Given the array find the maximum number of points you can score.

Input

The first line of the input contains T, the number of test cases.
The first line of each test case contains an integer n, denoting the size of the array.
Followed by n integers, \((a_1, a_2,...a_n)\).

Output

For each test case print in a new line the maximum points that can be scored.

Constraints

\(1 \le T \le 10\)
\(1 \le n \le 10^5\)
\(0 \le a_i \le 10^5\)