Вам задано некоторое количество запросов. В i-м запросе дано положительное целое число ni. Надо представить ni в виде суммы максимального количества составных слагаемых и вывести это количество, либо вывести -1, если такое представление невозможно.
Составными называются натуральные числа большие 1, не являющиеся простыми, то есть, имеющие натуральные делители, отличные от 1 и самого числа.
Выходные данные
Для каждого запроса выведите максимальное количество слагаемых в корректном разбиении на составные слагаемые или -1, если такого разбиения не существует.
Примечание
12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, но в первом разбиении больше количество слагаемых
8 = 4 + 4, 6 нельзя разбить на меньшие составные слагаемые.
1, 2, 3 меньше любого составного числа, поэтому для них не существует корректных разбиений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
12
|
3
|
|
2
|
2
6
8
|
1
2
|
|
3
|
3
1
2
3
|
-1
-1
-1
|