import java.io.*;
class dec
{
public static void main(String ar[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
int a[]=new int[t];
char dig[]={‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’};
int i,j;
String s="",w="";
int r;
int c[]=new int[t];
if(t>=1 && t<=64)
{
for(i=0;i<t;i++)
{
a[i]=Integer.parseInt(br.readLine());
while(a[i]>0)
{
r=a[i]%8;
s=dig[r]+s;
a[i]=a[i]/8;
}
for(j=0;j<s.length();j++)
{
w=s.charAt(j)+w;
}
if(s.compareTo(w)==0)
{c[i]=1;}
}
for(i=0;i<t;i++)
{
if(c[i]==1)
{
System.out.println("1");
}
else
{ System.out.println("-1");
}
}
}
}
}