import math
T = int(input())
for i in range(T):
    s = int(input())
    a = int(math.isqrt(s))
    if a*a == s:
        print(0)
    else:
        print(3)