Arun has an integer N. His friend likes the number 1, so Arun wants to reduce N to 1.

To do so, he can perform the following move several times (possibly, zero):
Pick two integers X and Y such that X+Y is even and X^{Y} is a divisor of N. Then, replace N by \dfrac{N}{X^{Y}}

Note that at each step, X^{Y} only needs to be a divisor of the *current* value of N, and not necessarily a divisor of the integer Arun initially started with.

Find the minimum number of moves Arun needs to reduce N to 1. If it is not possible to reduce N to 1 using the given operation, print -1 instead.

------ Input Format ------ 

- The first line of input will contain an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input containing one integer N.

------ Output Format ------ 

For each test case, output on a new line the answer — the minimum number of moves needed to reduce N to 1, or -1 if it is not possible to do so.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{18}$

----- Sample Input 1 ------ 
2
25
24

----- Sample Output 1 ------ 
1
-1
----- explanation 1 ------ 
Test case $1$: Choose $X = 25$ and $Y = 1$. $X+Y = 26$ is even, and $X^{Y} = 25$ is a divisor of $N = 25$ so this is a valid choice of $X$ and $Y$. Dividing $N$ by $X^{Y}$ leaves us with $\frac{25}{25} = 1$ and we are done.

Test case $2$: It can be shown that no matter which moves are made, $24$ cannot be reduced to $1$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
		continue
	num2 = 0
	while n % 2 == 0:
		num2 += 1
		n //= 2
	if num2 == 0:
		print(1)
	elif num2 % 2 == 0 and n != 1:
		ans = 2
		for i in range(2, num2 + 1):
			if num2 % i == 0:
				if (n ** (1 / i)).is_integer() and (2 ** (num2 / i) * n ** (1 / i) + i) % 2 == 0:
					ans = 1
					break
		print(ans)
	elif num2 % 2 == 0 and n == 1:
		print(1)
	else:
		print(-1)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	r = math.sqrt(n)
	if n % 2 == 1:
		print(min(n - 1, 1))
	elif r == math.floor(r):
		print(1)
	else:
		while n >= 4 and n % 4 == 0:
			n /= 4
		if n == 1:
			print(1)
		elif n % 2 == 1:
			print(2)
		else:
			print(-1)


import math

def check(n):
	if n == 1:
		return 0
	cnt = 0
	while n % 2 == 0:
		n //= 2
		cnt += 1
	if cnt == 0:
		return 1
	elif cnt % 2 == 1:
		return -1
	x = int(math.sqrt(n))
	if x * x == n:
		return 1
	return 2
for _ in range(int(input())):
	n = int(input())
	print(check(n))


import math
for _ in range(int(input())):
	n = int(input())
	t = n
	x = math.sqrt(n)
	flag = 0
	count = 0
	while flag != 1:
		if t % 2 == 0:
			t = t // 2
			count += 1
		else:
			flag = 1
	if n == 1:
		print(0)
	elif n % 2 == 1:
		print(1)
	elif count % 2 == 1:
		print(-1)
	elif int(x) * int(x) == n:
		print(1)
	else:
		print(2)


import math
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(0)
		continue
	(bit, Y) = (0, N)
	while Y % 2 == 0:
		Y //= 2
		bit += 1
	if bit == 0:
		print(1)
	elif bit & 1:
		print(-1)
	else:
		x = int(math.sqrt(N))
		print(1 if x * x == N else 2)


import math
n = int(input())
for i in range(n):
	m = int(input())
	if m == 1:
		print('0')
	elif m % 2 != 0:
		print('1')
	elif math.sqrt(m) == int(math.sqrt(m)):
		print('1')
	else:
		a = [2]
		x = m
		while x % 2 == 0:
			x //= 2
			if x % 2 == 0:
				a.append(2)
			elif x != 1:
				a.append(x)
		if a.count(2) % 2 != 0:
			print('-1')
		elif a[-1] % 2 == 0:
			print('1')
		else:
			print('2')


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
		continue
	k = 0
	while n % 2 == 0:
		n //= 2
		k += 1
	if k % 2 == 1:
		print(-1)
	elif k == 0:
		print(1)
	elif n == int(sqrt(n)) ** 2:
		print(1)
	else:
		print(2)


def np2(x):
	n = 0
	while x % 2 == 0:
		x = x // 2
		n += 1
	return (n, x)
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	else:
		(p, nn) = np2(n)
		if p % 2 != 0:
			print(-1)
		else:
			nr = nn ** (1 / 2)
			if nr.is_integer():
				print(1)
			else:
				print(2)


from math import sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 == 1:
		print(1)
	elif int(sqrt(n)) ** 2 == n:
		print(1)
	else:
		cnt = 0
		while n % 2 == 0:
			cnt += 1
			n = n // 2
		if cnt % 2 == 1:
			print(-1)
		elif n == 1:
			print(1)
		else:
			print(2)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
		continue
	count = 0
	while n % 2 == 0:
		count += 1
		n = n // 2
	if count == 0:
		print(1)
		continue
	elif count % 2 == 1:
		print(-1)
		continue
	x = int(n ** (1 / 2))
	if x * x == n:
		print(1)
	else:
		print(2)


import sys
import os
import math
from collections import *
import bisect
from heapq import *
from itertools import permutations
if os.path.exists('input.txt') and os.path.exists('output.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def lcm(a, b):
	k1 = math.gcd(a, b)
	k2 = a * b
	return k2 // k1

def inp():
	return map(int, input().strip().split(' '))

def lis():
	return list(inp())
mod = 998244353

def prim(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
ma = 2 * (10 ** 5 + 1)

def update(ind, val, n):
	while ind <= n:
		fenwick[ind] += val
		ind += ind & -ind

def qsum(ind):
	ans = 0
	while ind > 0:
		ans += fenwick[ind]
		ind -= ind & -ind
	return ans

def dfs(adj, vis, u, l):
	vis[u] = 1
	l.add(u)
	for i in adj[u]:
		if vis[i] == 0:
			dfs(adj, vis, i, l)
mod = 10 ** 9 + 7
ma = 1002
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(i, j, arr, vis, n, m):
	vis[i][j] = 1
	for x in range(4):
		mx = i + dx[x]
		my = j + dy[x]
		if mx >= 0 and mx < n and (my >= 0) and (my < m) and (vis[mx][my] == 0):
			if arr[i][j] >= arr[mx][my]:
				dfs(mx, my, arr, vis, n, m)

def dfs(a, vis, node, c):
	vis[node] = 1
	c[0] += 1
	if vis[a[node]] == 0:
		dfs(a, vis, a[node], c)
mod = 998244353

def f(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0
mod = 10 ** 9 + 7

def finv(p, q):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def solve():
	n = int(input())
	cnt = 0
	c = n
	while c % 2 == 0:
		cnt += 1
		c //= 2
	if n == 1:
		print(0)
		return
	if n & 1:
		print(1)
		return
	if cnt & 1:
		print(-1)
		return
	if math.sqrt(n) % 1 == 0:
		print(1)
		return
	print(2)
t = int(input())
for _ in range(t):
	solve()


import math
try:

	def fun(n):
		cnt = 0
		while n % 2 == 0:
			n = n // 2
			cnt += 1
		return cnt
	for _ in range(int(input())):
		n = int(input())
		if n == 1:
			print(0)
		elif n & 1:
			print(1)
		elif fun(n) & 1:
			print(-1)
		elif math.ceil(math.sqrt(n)) == math.floor(math.sqrt(n)):
			print(1)
		elif math.ceil(math.sqrt(n)) != math.floor(math.sqrt(n)):
			print(2)
except:
	pass


import math

def solve():
	n = int(input())
	if n == 1:
		print(0)
		return
	if n % 2 == 1:
		print(1)
		return
	cnt = 0
	while n > 0 and n % 2 == 0:
		cnt += 1
		n = n // 2
	if cnt % 2 == 1:
		print(-1)
		return
	s = int(math.sqrt(n))
	if s * s == n:
		print(1)
	else:
		print(2)
for _ in range(int(input())):
	solve()


import itertools
import collections, math
from collections import defaultdict
from collections import Counter
import sys
import heapq
from heapq import *
for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
		continue
	if n % 2 == 1:
		print(1)
	elif n ** 0.5 == int(n ** 0.5):
		print(1)
	else:
		p2 = 0
		N = n
		while n % 2 == 0:
			p2 += 1
			n = n // 2
		if p2 % 2 == 0:
			print(1 + int(n > 1))
		else:
			print(-1)


t = int(input())

def fac(n):
	if n % 2 != 0:
		return 0
	return 1 + fac(n // 2)
import math
for _ in range(t):
	n = int(input())
	sq = int(math.sqrt(n))
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	elif n % 2 == 0 and sq * sq == n:
		print(1)
	elif n % 2 == 0 and fac(n) % 2 == 0:
		print(2)
	else:
		print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	m = n
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	else:
		c = 0
		while n % 2 == 0:
			n = n // 2
			c += 1
		if c % 2 == 0:
			n1 = int(math.sqrt(m))
			if n1 * n1 == m:
				print(1)
			else:
				print(2)
		else:
			print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('0')
		continue
	c = 0
	res = 0
	m = n
	while m % 2 == 0:
		c += 1
		m = m // 2
	if c == 0:
		print('1')
	elif c % 2 == 1:
		print('-1')
	else:
		x = int(math.sqrt(n))
		if x * x == n:
			print('1')
		else:
			print('2')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	m = n
	flag = 0
	c = 0
	while m % 2 == 0:
		c = c + 1
		m = m // 2
	chk = int(math.sqrt(n))
	if n == 1:
		print(0)
	elif c == 0:
		print(1)
	elif chk * chk == n:
		print(1)
	elif c % 2 == 0 and m == 1:
		print(1)
	elif c % 2 == 0:
		print(2)
	elif c % 2 == 1:
		print(-1)


import math as m

def countTwo(n):
	c = 0
	while n % 2 == 0:
		c += 1
		n = n // 2
	return c
for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	else:
		temp = int(m.sqrt(n))
		if temp * temp == n:
			print(1)
		else:
			x = countTwo(n)
			if int(x) % 2 == 1:
				print(-1)
			else:
				print(2)


import math

def twos(n):
	cnt = 0
	while n % 2 == 0:
		n = n // 2
		cnt += 1
	return cnt
t = int(input())
for i in range(0, t):
	n = int(input())
	if n == 1:
		print('0')
	elif n % 2 != 0:
		print('1')
	else:
		x = int(math.sqrt(n))
		if x * x == n:
			print('1')
		else:
			two = twos(n)
			if two % 2 == 0:
				print('2')
			else:
				print('-1')


import math

def countTwo(n):
	c = 0
	while n % 2 == 0:
		c += 1
		n = n // 2
	return c
t = int(input())
twos = 0
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	else:
		temp = int(math.sqrt(n))
		if temp * temp == n:
			print(1)
		else:
			twos = countTwo(n)
			if twos % 2 == 1:
				print(-1)
			else:
				print(2)


T = int(input())
for _ in range(T):
	n = int(input())
	if n == 1:
		print(0)
		continue
	if n & 1 or n ** 0.5 == int(n ** 0.5):
		print(1)
		continue
	power_of_two = 0
	while True:
		if n % 2 == 0:
			n = n // 2
			power_of_two += 1
		else:
			break
	if power_of_two & 1:
		print(-1)
		continue
	else:
		print(2)


import math
for _ in range(int(input())):
	n = int(input())

	def prime2(n):
		d2 = {}
		while n % 2 == 0:
			if 2 not in d2:
				d2[2] = 1
			else:
				d2[2] = d2[2] + 1
			n = n // 2
		return d2

	def isPerfectSquare(x):
		if x >= 0:
			sr = int(math.sqrt(x))
			return sr * sr == x
		return false
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	elif prime2(n)[2] % 2 != 0:
		print(-1)
	elif isPerfectSquare(n) == 1:
		print(1)
	else:
		print(2)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def Solution():
	pass

def main():
	for _ in range(get_int()):
		n = get_int()
		if n == 1:
			print(0)
			continue
		if n % 2:
			print(1)
		else:
			pft = 0
			t = n
			while n % 2 == 0:
				pft += 1
				n = n // 2
			if pft % 2:
				print(-1)
				continue
			x = int(math.sqrt(t))
			if x * x == t:
				print(1)
			else:
				print(2)
main()


from math import sqrt
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n & 1:
		print(1)
	else:
		s = int(sqrt(n))
		if s * s == n:
			print(1)
			continue
		count = 0
		while n & 1 == 0:
			n //= 2
			count += 1
		if count & 1:
			print(-1)
		else:
			print(2)


import math

def solve(n):
	if n == 1:
		return 0
	if n % 2 == 1:
		return 1
	else:
		t = math.floor(math.sqrt(n)) - math.ceil(math.sqrt(n))
		if t == 0:
			return 1
		else:
			num = n
			cnt = 0
			while num % 2 == 0:
				num //= 2
				cnt += 1
			if cnt % 2 == 0:
				return 2
			else:
				return -1
for test in range(int(input())):
	n = int(input())
	print(solve(n))


from math import sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n & 1:
		print(1)
	else:
		s = int(sqrt(n))
		if s * s == n:
			print(1)
			continue
		c = 0
		while n & 1 == 0:
			n //= 2
			c += 1
		if c & 1:
			print(-1)
		else:
			print(2)


from math import sqrt
from collections import defaultdict
from collections import OrderedDict
from collections import Counter
from collections import ChainMap

def getlist():
	return list(map(int, input().split()))

def getinp():
	return map(int, input().split())

def solution(n):
	if n == 1:
		return 0
	count = 0
	while n % 2 == 0:
		n = n // 2
		count += 1
	if count == 0:
		return 1
	if count & 1:
		return -1
	elif n == 1:
		return 1
	else:
		x = n ** 0.5
		if x == int(x):
			return 1
		return 2

def main():
	for _ in range(int(input())):
		n = int(input())
		print(solution(n))
main()


import math

def solution(n):
	if n == 1:
		return 0
	count = 0
	while n % 2 == 0:
		n = n // 2
		count += 1
	if count == 0:
		return 1
	if count & 1:
		return -1
	elif n == 1:
		return 1
	else:
		x = n ** 0.5
		if x == int(x):
			return 1
		return 2
t = int(input())
for _ in range(t):
	n = int(input())
	print(solution(n))


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def itr(l, k):
	c = 0
	for ele in l:
		if ele % 2 == k:
			c += 1
	return c - 1

def county(l, k):
	c = 0
	for ele in l:
		if ele % 2 == k:
			c += 1
	if c == 1:
		return True
	return False

def solve():
	n = int(input())
	c = 0
	if n == 1:
		return 0
	while n % 2 == 0:
		c += 1
		n //= 2
	if c % 2 == 1:
		return -1
	if math.sqrt(n) == int(math.sqrt(n)):
		return 1
	if c == 0:
		if n == 1:
			return 0
		else:
			return 1
	if n == 1:
		return 1
	return 2
for _ in range(int(input())):
	print(solve())


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2:
		print(1)
	elif n & ~(n - 1) == n:
		if len(bin(n)) % 2:
			print(1)
		else:
			print(-1)
	elif int(math.sqrt(n)) * int(math.sqrt(n)) == n:
		print(1)
	else:
		count = 0
		while n % 2 == 0:
			n //= 2
			count += 1
		if count % 2:
			print(-1)
		else:
			print(2)


for T in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	else:
		count = 0
		while n % 2 == 0:
			n = n // 2
			count += 1
		if count % 2 == 0 and n ** 0.5 == int(n ** 0.5):
			print(1)
		elif count % 2 == 0 and n == 1:
			print(1)
		elif count % 2 == 0 and n != 1:
			print(2)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n & 1:
		print(1)
	else:
		c = 0
		while not n & 1:
			c += 1
			n //= 2
		if c & 1:
			print(-1)
		elif n ** 0.5 == int(n ** 0.5):
			print(1)
		elif n > 1:
			print(2)
		else:
			print(1)


import math
for _ in range(int(input())):
	num = int(input())
	if num == 1:
		print(0)
		continue
	if num % 2 != 0:
		print(1)
		continue
	else:
		count = 0
		n = num
		while n % 2 == 0:
			count += 1
			n //= 2
		if count % 2:
			print(-1)
			continue
		if int(math.sqrt(num)) ** 2 == num or n == 1:
			print(1)
			continue
	print(2)


for _ in range(int(input())):
	n = int(input())
	num = n
	if n == 1:
		print(0)
		continue
	count2 = 0
	if n % 2:
		print(1)
		continue
	while n % 2 == 0:
		count2 += 1
		n //= 2
	if count2 % 2:
		print(-1)
		continue
	x = int(num ** 0.5)
	if n == 1 or x * x == num:
		print(1)
		continue
	print(2)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	if n == 1:
		ans = 0
	elif n % 2:
		ans = 1
	else:
		x = 0
		temp = n
		while temp % 2 == 0:
			x += 1
			temp = temp // 2
		if x % 2 == 0:
			n1 = math.floor(math.sqrt(n))
			if n1 ** 2 == n:
				ans = 1
			else:
				ans = 2
		else:
			ans = -1
	print(ans)


import math
addy = int(input())
for i in range(addy):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2:
		print(1)
	else:
		x = 0
		temp = n
		while temp % 2 == 0:
			x += 1
			temp = temp // 2
		if x % 2 == 0:
			a = math.floor(n ** 0.5)
			b = math.floor(n ** 0.5)
			if a ** 2 == n or b ** 2 == n:
				print(1)
			else:
				print(2)
		else:
			print(-1)


from math import sqrt
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
		continue
	if n % 2 == 1:
		print(1)
		continue
	ct = 0
	while n % 2 == 0:
		ct += 1
		n //= 2
	if ct % 2:
		print(-1)
		continue
	sr = int(sqrt(n))
	if n == 1:
		print(1)
	elif sr * sr == n:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 == 1:
		print(1)
	elif pow(n, 0.5) == int(pow(n, 0.5)):
		print(1)
	else:
		c = 0
		for i in range(64, 1, -2):
			p = pow(2, i)
			while n > 0 and n % p == 0:
				n //= p
				c += 1
		if n == 1:
			print(c)
		elif n % 2 == 1:
			print(c + 1)
		else:
			print(-1)


for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(0)
		continue
	if N % 2:
		print(1)
		continue
	if int(N ** 0.5) * int(N ** 0.5) == N:
		print(1)
		continue
	ans = 0
	num2 = 0
	while N % 2 == 0:
		N //= 2
		num2 += 1
	if num2 % 2:
		print(-1)
		continue
	if num2:
		ans += 1
	if N != 1:
		ans += 1
	print(ans)


import sys
import re
f = map(int, sys.stdin)
next(f)
for n in f:
	m = re.match('0*', bin(n)[::-1])
	if m.end() - m.start() & 1:
		print(-1)
	else:
		print(2 - (n == 1) - (n % 2 or n == int(n ** 0.5) ** 2))


import sys
f = map(int, sys.stdin)
next(f)
for n in f:
	s = bin(n)
	if len(s) - len(s.rstrip('0')) & 1:
		print(-1)
	else:
		print(2 - (n == 1) - (n % 2 or n == int(n ** 0.5) ** 2))


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		if n == 1:
			print(0)
			continue
		if n % 2 != 0:
			print(1)
			continue
		res = 0
		if int(math.sqrt(n)) % 2 == 0 and int(math.sqrt(n)) == math.sqrt(n):
			print(1)
			continue
		while n % 2 == 0:
			res += 1
			n //= 2
		if res % 2 == 0:
			if n == 1:
				print(1)
				continue
			print(2)
		else:
			print(-1)
main()


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
		continue
	if n % 2 == 1:
		print(1)
		continue
	if int(sqrt(n)) * int(sqrt(n)) == n:
		print(1)
		continue
	while n % 4 == 0:
		n = n // 4
	if n == 1:
		print(1)
		continue
	if n % 2 == 1:
		print(2)
		continue
	print(-1)


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2:
		print(1)
	elif pow(int(math.sqrt(n)), 2) == n:
		print(1)
	else:
		cnt = 0
		while n % 2 == 0:
			cnt += 1
			n = n // 2
		if not n & n - 1:
			if cnt % 2 == 0:
				print(1)
			else:
				print(-1)
		elif cnt % 2 == 0:
			print(2)
		else:
			print(-1)


import math
for i in range(int(input())):
	n = int(input())
	c = 0
	while n % 2 == 0:
		n = n // 2
		c += 1
	if c == 0:
		if n == 1:
			print(0)
		else:
			print(1)
	elif c % 2 == 0:
		if n == 1:
			print(1)
		elif math.sqrt(n) == int(math.sqrt(n)):
			print(1)
		else:
			print(2)
	else:
		print(-1)


from math import sqrt
t = int(input())
while t:
	n = int(input())
	if n == 1:
		print(0)
	elif n & 1:
		print(1)
	else:
		val = 2
		ind = 1
		for i in range(1, n):
			if n // val & 1:
				ind = i
				break
			val <<= 1
		if ind & 1:
			print(-1)
		elif sqrt(n) == int(sqrt(n)):
			print(1)
		else:
			print(2)
	t -= 1


def solve():
	N = int(input())
	if N == 1:
		print(0)
	elif N % 2 == 1:
		print(1)
	else:
		c = 0
		k = N ** 0.5
		if k == int(k):
			print(1)
			return
		while N % 2 == 0:
			c += 1
			N //= 2
		if c % 2:
			print(-1)
		else:
			print(1 + int(N > 1))
for _ in range(int(input())):
	solve()


from math import sqrt

def soln(n: int) -> int:
	if n == 1:
		return 0
	if n & 1:
		return 1
	if int(sqrt(n)) * int(sqrt(n)) == n:
		return 1
	cnt = 0
	while n:
		if not n & 1:
			cnt += 1
			n //= 2
		else:
			break
	if cnt & 1:
		return -1
	if n:
		return 2
	return 1
tc = int(input())
while tc:
	tc -= 1
	n = int(input())
	print(soln(n))


import math
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 == 1:
		print(1)
	elif n ** 0.5 % 1 == 0:
		print(1)
	elif math.log2(n) % 2 == 0:
		print(1)
	elif math.log2(n & ~(n - 1)) % 2 == 0:
		print(2)
	else:
		print(-1)


import math

def isSqrt(num):
	val = num ** 0.5
	return val == int(val)

def factorize(n):
	if n == 1:
		return 0
	if n & 1 or isSqrt(n):
		return 1
	count = 0
	while n % 2 == 0:
		count += 1
		n = n // 2
	if count & 1:
		return -1
	if n == 1:
		return 1
	return 2
t = int(input())
for _ in range(t):
	n = int(input())
	ans = factorize(n)
	print(ans)


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdout = open('output.txt', 'w')
	sys.stdin = open('input.txt', 'r')

def issqrt(n):
	sqrt = n ** 0.5
	return sqrt == int(sqrt)

def solve(n):
	if n == 1:
		return 0
	if n % 2 != 0 or issqrt(n):
		return 1
	i = 0
	while n % 2 == 0:
		n = n // 2
		i += 1
	if i % 2 != 0:
		return -1
	return 1 if n == 1 or issqrt(n) else 2

def main():
	sys.setrecursionlimit(10 ** 8)
	for _ in range(int(input())):
		n = int(input())
		result = solve(n)
		print(result)
main()


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 != 0:
		print(1)
	else:
		j = 0
		while True:
			if n % 2 == 0:
				n = n // 2
				j += 1
			else:
				break
		if j % 2:
			print(-1)
		elif int(math.sqrt(n)) == math.sqrt(n):
			print(1)
		else:
			print(2)


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		if n == 1:
			print(0)
		else:
			print(1)
	else:
		count = 0
		while n % 2 == 0:
			count += 1
			n //= 2
		if count % 2 == 0 and n > 1:
			a = math.sqrt(n)
			if a - int(a) == 0:
				print(1)
			else:
				print(2)
		elif count % 2 == 0 and n == 1:
			print(1)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		if n == 1:
			print(0)
		else:
			print(1)
	else:
		i = 2
		nn = n
		c = 0
		while nn % 2 == 0:
			nn //= 2
			c += 1
		if c % 2 == 1:
			print(-1)
		else:
			flag = False
			sq = pow(n, 0.5)
			sq = int(sq)
			if sq * sq == n:
				flag = True
			elif nn == 1:
				flag = True
			if flag:
				print(1)
			else:
				print(2)


from sys import stdin, stdout
from collections import defaultdict, Counter
import math
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	if n == 1:
		print(0)
		continue
	if n % 2 == 1:
		print(1)
		continue
	if math.ceil(math.sqrt(n)) == math.floor(math.sqrt(n)):
		print(1)
		continue
	cnt = 0
	while n % 2 == 0:
		cnt += 1
		n = n // 2
	if cnt % 2 == 1:
		print(-1)
		continue
	print(2)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def solve(t):
	n = readInts()
	if n == 1:
		print(0)
	elif n & 1:
		print(1)
	else:
		p = 0
		tmp = n
		while tmp % 2 == 0:
			p += 1
			tmp = tmp // 2
		if p & 1:
			print(-1)
		elif math.floor(math.sqrt(n)) ** 2 == n:
			print(1)
		else:
			print(2)

def main():
	t = 1
	sys.setrecursionlimit(12000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 == 1 or math.sqrt(n) % 1.0 == 0:
		print(1)
	else:
		twos = 0
		while n % 2 ** twos == 0:
			twos += 1
		if (twos - 1) % 2 == 0:
			print(2)
		else:
			print(-1)


def p2(n):
	ans = 0
	while n & 1 == 0 and n > 0:
		ans += 1
		n >>= 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	c = p2(n)
	r = int(n ** 0.5)
	ans = 0
	if c & 1:
		ans = -1
	elif n == 1:
		ans = 0
	elif r * r == n:
		ans = 1
	else:
		if c != 0:
			ans += 1
		if n // 2 ** c != 1:
			ans += 1
	print(ans)


def counter(n):
	c = 0
	while n % 2 == 0:
		c += 1
		n //= 2
	return c
for _ in range(int(input())):
	x = int(input())
	sqrt = int(x ** 0.5)
	if x == 1:
		print(0)
	elif x % 2 == 1:
		print(1)
	elif sqrt ** 2 == x:
		print(1)
	else:
		count = counter(x)
		if count % 2 == 0:
			print(2)
		else:
			print(-1)


for _ in range(int(input())):

	def fac(n):
		c = 0
		while n % 2 == 0:
			c += 1
			n //= 2
		return c
	n = int(input())
	sq = int(n ** 0.5)
	if n == 1:
		print(0)
	elif n % 2 == 1:
		print(1)
	elif n % 2 == 0 and sq ** 2 == n:
		print(1)
	elif n % 2 == 0 and fac(n) % 2 == 0:
		print(2)
	else:
		print(-1)


import math
pow4 = [4 ** x for x in range(1, 31)]
for x in range(int(input())):
	n = int(input())
	if n & 1:
		if n == 1:
			print(0)
		else:
			print(1)
	elif math.sqrt(n) == int(math.sqrt(n)):
		print(1)
	else:
		cnt = 0
		flag = True
		while flag:
			temp = -1
			for x in pow4:
				if n % x == 0:
					temp = x
			if temp == -1:
				flag = False
			else:
				n = n // temp
				cnt += 1
		if n & 1:
			if n != 1:
				cnt += 1
			print(cnt)
		else:
			print(-1)


def fun(n):
	if int(n ** 0.5) ** 2 == n:
		return 1
	tp = 0
	while n % 2 == 0:
		tp += 1
		n = n // 2
	if tp % 2 == 0:
		if n == 1:
			return 1
		return 2
	return -1
T = int(input())
for _ in range(T):
	n = int(input())
	if n == 1:
		print(0)
		continue
	if n % 2 == 1:
		print(1)
		continue
	print(fun(n))


import math
t = int(input())
for i in range(t):
	xyz = 0
	n = int(input())
	k = math.sqrt(n)
	k = int(k)
	if n == 1:
		print(0)
		continue
	if k * k == n:
		print(1)
		continue
	if n & 1:
		print(1)
		continue
	while not n & 1:
		xyz += 1
		n >>= 1
	if xyz % 2 != 0:
		print(-1)
	elif n == 1:
		print(1)
	else:
		print(2)


import math

def isPerfectSquare(x):
	if x >= 0:
		sr = int(math.sqrt(x))
		return sr * sr == x
	return false
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0)
	elif n % 2 == 1:
		print(1)
	elif isPerfectSquare(n) == 1:
		print(1)
	else:
		c = 0
		par = n % 2
		while par == 0 and n > 0:
			c += 1
			n = n // 2
			par = n % 2
		par2 = c % 2
		if par2 == 0:
			if n == 1:
				print(1)
			else:
				print(2)
		else:
			print(-1)