Today is Anik's Birthday. Saad wants to give Anik an array as birthday present.
But Anik is afraid of Odd numbers.He will get scared if the G.C.D of all the numbers of the array is an odd number.
So Saad wants to remove minimum possible numbers so that The G.C.D of all the numbers of the array becomes even number. And you are ( As always) the only one who can help Saad.
If it is impossible to make the G.C.D an even number print -1.
G.C.D(Greatest Common Divisor) of some numbers means the greatest number that can divide the given numbers.
Input
In the first line, There will be an integer N, (the size of the array)
In the next line N numbers will be given.
(1 <= N <= 100000)
(1 <= Given Numbers <= 1000000)
Output
Print the minimum possible numbers as described in the statement if it is possible to make the G.C.D an even number. If it is not possible, then print -1.
Samples
| Input | Output |
|---|---|
2 1 2 | 1 |
| Input | Output |
|---|---|
5 1 1 2 4 2 | 2 |
