Chef In Infinite Plane solution codechef

Chef In Infinite Plane solution codechef


Chef has an integer sequence A1,A2,,ANA1,A2,…,AN. For each index ii (1iN1≤i≤N), Chef needs to divide AiAi into two positive integers xx and yy such that x+y=Aix+y=Ai, then place this as a point (x,y)(x,y) in the infinite 22-dimensional coordinate plane. Help Chef to find the maximum number of distinct points that can be put in the plane, if he optimally splits the values AiAi. Note that Chef can only perform one split for each index.

Note: Please use fast input/output methods for this problem.

Input Format

  • The first line contains a single integer TT – the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the maximum number of distinct points there can be in the infinite plane.

Constraints

  • 1T101≤T≤10
  • 1N21051≤N≤2⋅105
  • 2Ai1052≤Ai≤105

Sample Input 1 

2
6
2 2 4 4 2 6 
2
16 8

Sample Output 1 

4
2

Explanation

Test Case 1: Chef can divide A1A1 as (1,1)(1,1)A2A2 as (1,1)(1,1)A3A3 as (1,3)(1,3)A4A4 as (2,2)(2,2)A5A5 as (1,1)(1,1)A6A6 as (2,4)(2,4). Ignoring duplicates, there are 44 distinct points, which is the maximum possible.

Test Case 2: Chef can divide A1A1 as (8,8)(8,8)A2A2 as (4,4)(4,4).

Leave a Comment