require "prime"
T = gets.to_i
T.times do
    n = gets.to_i
    n /= 2 while n % 2 == 0
    n /= 5 while n % 5 == 0
    n /= 3 if n % 3 == 0
    len = Prime.prime_division(n).inject(1) { |prod, (p, e)| prod.lcm(p - 1) * p**(e-1) }
    puts len
end