Problem Setter: Al Shahreyaj

A 3rd year CSE student of BSMRSTU

Let me tell you a story. Once I met with Sefuda in a bar. He was drinking Mod then. I tried to talk with him.

Me: Hi, Sefuda. How are you?

Sefuda: I’m good. Listen kid. Now I’m drinking Mod. And you know while drinking mod a lot of hard problems come to my mind. Now I’m going to tell you one and you have to solve it.

Me: Ok, tell me.

Sefuda:

A number will be given. You can write the number as a sum of few positive numbers. Find the minimum number of integers needed to write the given integer such that the difference between the number of odd and even integers will be zero. Suppose, the number is 9. You can write it as 4+5. As, 4 is even and 5 is odd. The difference is 1-1 = 0. So, the minimum number is 2. If it’s not possible, print -1. Remember one special case, Zero won’t be counted as odd or even.

I tried then a lot but I couldn’t solve it. Hope you will solve it for me.

Input Format

Input starts with an integer N (1 ≤ N ≤ 100000) denoting the number of test case. Next N lines contains an integer. Each of these integers will be in the range of 1 and 10^12.

Output Format

For each test case output the result.

Samples