Кусок цветного глазурованного стекла размером $n$ падает с высоты и разбивается на сверкающие осколки, размер каждого из которых является положительным целым числом.

Ая перебирает эти сверкающие осколки. В её глазах осколок размера $x$ является «красивым» тогда и только тогда, когда $x$ — нечетное число, большее 1.

При условии, что все осколки являются «красивыми», Ая хочет узнать максимальное количество осколков. Если ситуации, при которой все осколки являются «красивыми», не существует, выведите -1.

Входные данные

Задача содержит несколько наборов входных данных. В первой строке задано одно целое число $T$ ($1 \le T \le 10^4$), количество наборов данных.

Для каждого набора данных: В одной строке задано одно целое число $n$ ($1 \le n \le 10^9$), представляющее размер стекла, то есть сумму размеров всех осколков.

Выходные данные

Для каждого набора данных: Выведите одно целое число — максимальное количество осколков при условии, что все они являются «красивыми». Если такой ситуации не существует, выведите -1.

Примеры

Входные данные 1

6
1
3
5
7
8
9

Выходные данные 1

-1
1
1
1
2
3

Примечание

Для $n = 3$, $n = 5$, $n = 7$ максимальное количество осколков очевидно равно 1. Для $n = 8$ максимальное количество осколков равно 2, при этом размеры осколков равны 3 и 5. Для $n = 9$ максимальное количество осколков равно 3, при этом размеры осколков равны 3, 3 и 3.