import math
fib_nums = [0, 1]
for i in range(2,60):
fib_nums.append(fib_nums[i-1]+fib_nums[i-2])
d_nums=[fib_nums[i]%10 for i in range(60)]
T=int(input())
for i in range(T):
n = int(input())
k=int(math.log2(n))
l=(2 ** k)-1
m=l%60
print(d_nums[m])
aW1wb3J0IG1hdGgKZmliX251bXMgPSBbMCwgMV0KZm9yIGkgaW4gcmFuZ2UoMiw2MCk6CglmaWJfbnVtcy5hcHBlbmQoZmliX251bXNbaS0xXStmaWJfbnVtc1tpLTJdKQpkX251bXM9W2ZpYl9udW1zW2ldJTEwIGZvciBpIGluIHJhbmdlKDYwKV0gClQ9aW50KGlucHV0KCkpCmZvciBpIGluIHJhbmdlKFQpOgoJbiA9IGludChpbnB1dCgpKQoJaz1pbnQobWF0aC5sb2cyKG4pKQoJbD0oMiAqKiBrKS0xCgltPWwlNjAKCXByaW50KGRfbnVtc1ttXSk=