数学课上，老师出了一个题目给全班同学做，题目是这样的：有一个正整数n，请将n分解成多个合数，最多能分成多少个合数？比如12 = 4+4+4 = 4+8 = 6+6 = 12，一共有4种分法，最多的是第一个种，可以分成3个4，所以答案是3。如果分解不了，则输出 -1。避免有些同学投机取巧，直接输出-1。现在将难度升级了，给出多组数据，每个正整数对应的答案是多少？

第一行为一个正整数q，表示有q组数据（ 1<=q<=10⁵），
接下来有q行，每行一个正整数 n_i（1<=n_i<=10⁹），表示要分解的数。

每行输出一个整数，表示n_i能够最多分解的合数的个数。
如果分解不了，则输出 -1。

对于30%的数据：1 ≤ q ≤ 100，1 ≤ n_{i ≤ 1000}
对于60%的数据：1 ≤ q _{≤ 1000，1 ≤ ni ≤ 10}⁶
对于100%的数据：1 ≤ q _{≤ 10}⁵_{，1 ≤ ni ≤ 10}⁹

数学数论