Make the array even HackerEarth Question

 Make the array even

Max. score: 100

You are given an array A of N integers. If you make the array whole using the following operation, then what is the minimum number of operations required to make the entire array even?

Note: It can be proved that this is always possible.

Operation

Select an index  $1\le i<N$  and perform operation:

P=A_i+A_i+1; Q=A_i-A_i+1;

A_i=P; A_i+1=Q;

Input format

• The first line contains an integer T denoting the number of the test cases.
• In each test case:
  • The first line contains an integer N denoting the number of elements in the array.
  • The second line contains N space-separated integers of array A.

Output format

For each test case print a single line denoting the minimum number of operations required to make the whole array even.

Constraints

• $1\le T\le 20000$
• $2\le N\le 200000$
• $1\le A_i\le 1e9\mathrm{\forall }i\in [1,N]$
• Sum of N over all test cases will not exceed 200000

SAMPLE INPUT

 

1
4
1 3 2 2

SAMPLE OUTPUT

 

1

Explanation

If we choose index 1 A1=1+3=4 and A2=1-3=-2.

So only one operation is required to make array even.

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Score is assigned if any testcase passes.

Allowed Languages:Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic