N = gets.to_i

class Integer
    def modpow(n, p)
        return 1 if n.zero?
        return (self * self.modpow(n - 1, p)) % p if n.odd?
        (self * self % p).modpow(n / 2, p)
    end
end

N.times do
    p = gets.to_i

    if p == 2
        puts 2
        next
    end
    x = 1
    until 2.modpow(x, p) == x % p
        x = 2.modpow(x, p * (p - 1))
    end
    puts x
end