Un morceau de verre émaillé de taille $n$ tombe du ciel et se brise en éclats brillants, la taille de chaque éclat étant un entier positif.

Ling examine ces éclats scintillants. À ses yeux, un éclat de taille $x$ est considéré comme un « éclat magnifique » si et seulement si $x$ est un nombre impair supérieur à 1.

Sous la condition que tous les éclats soient des éclats magnifiques, Ling souhaite connaître le nombre maximal d'éclats. S'il est impossible que tous les éclats soient des éclats magnifiques, répondez par -1.

Entrée

Ce problème comporte plusieurs jeux de données. La première ligne contient un entier positif $T$ ($1 \le T \le 10^4$), représentant le nombre de jeux de données.

Pour chaque jeu de données : Une ligne contenant un entier positif $n$ ($1 \le n \le 10^9$), représentant la taille du verre émaillé, c'est-à-dire la somme des tailles de tous les éclats.

Sortie

Pour chaque jeu de données : Une ligne contenant un entier représentant le nombre maximal d'éclats sous la condition que tous les éclats soient des éclats magnifiques. S'il est impossible que tous les éclats soient des éclats magnifiques, affichez -1.

Exemples

Entrée 1

6
1
3
5
7
8
9

Sortie 1

-1
1
1
1
2
3

Remarque

Pour $n = 3$, $n = 5$, $n = 7$, le nombre maximal d'éclats est évidemment 1. Pour $n = 8$, le nombre maximal d'éclats est 2, les tailles des éclats étant alors 3 et 5. Pour $n = 9$, le nombre maximal d'éclats est 3, les tailles des éclats étant alors 3, 3 et 3.