Divisor game

0

0 votes
Mathematics, Easy-Medium, Factorization
Problem

You have been given an array consisting of n integers, (a1,a2,...an). 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 (a1,a2,...ak) and (ak+1,ak+2,...an). Then,
    ki=1f(ai)=ni=k+1f(aj), 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, (a1,a2,...an).

Output

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

Constraints

1T10
1n105
0ai105

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the first test case,
Partitioning the array is not possible, hence the maximum achievable score is 0.

For the second test case,
Partitioning the array into {0, 2, 3} and {2, 3}.
Discarding the first partition,
Partitioning the second array into {2} and {3}.
Total score = 1 + 1 = 2

Editor Image

?