C. Максимальное разбиение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано некоторое количество запросов. В i-м запросе дано положительное целое число ni. Надо представить ni в виде суммы максимального количества составных слагаемых и вывести это количество, либо вывести -1, если такое представление невозможно.

Составными называются натуральные числа большие 1, не являющиеся простыми, то есть, имеющие натуральные делители, отличные от 1 и самого числа.

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

В первой строке дано число q (1 ≤ q ≤ 105) — количество запросов

Далее идет q строк. В (i + 1)-й строке дано число ni (1 ≤ ni ≤ 109) — i-й запрос.

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

Для каждого запроса выведите максимальное количество слагаемых в корректном разбиении на составные слагаемые или -1, если такого разбиения не существует.

Примеры
Входные данные
1
12
Выходные данные
3
Входные данные
2
6
8
Выходные данные
1
2
Входные данные
3
1
2
3
Выходные данные
-1
-1
-1
Примечание

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, но в первом разбиении больше количество слагаемых

8 = 4 + 4, 6 нельзя разбить на меньшие составные слагаемые.

1, 2, 3 меньше любого составного числа, поэтому для них не существует корректных разбиений.