琴·古恩希尔德，蒙德城西风骑士团代理团长，四风守护中的南风之狮。身为西风骑士团的代理团长，琴一直忠于职守，为人们带来安宁。虽然并非天赋异禀，但通过刻苦训练，如今的她已然能够独当一面。当风魔龙的威胁开始临近，这位可靠的代理团长早已做好了准备，誓要守护蒙德。
雷泽，住在蒙德地区奔狼领，远离城市与人群，和狼一同生活的少年。直觉锐利，身姿迅捷。
琴团长这几天准备教一下雷泽数学，问了雷泽一个关于互质的问题。
互质是一个数学概念，两个数互质是指两个数的共同因子只有1。
琴团长提出了T次询问，每次询问给出一个正整数n，询问雷泽是否存在一个正整数x，满足x大于等于n/4向上取整，小于等于n/2向下取整，且x与n互质。
雷泽并不会数学，于是便向你求助。
输入描述:
第一行只有一个正整数T，表示询问的数量。 接下来的T行，每行一个正整数n，表示询问的数字。
1 <= T <= 10^6，4 <= n <= 10^16
输出描述:
本题采用special judge。
输出一共T行，每次询问分别输出一个整数，如果存在一个满足上述条件的x，输出这个x，否则输出-1。