gets;$<.map{|e| n,m=e.split.map &:to_i a=0 if (2..Math.sqrt(m)).each{|b| (n.downto(a=1){|n|a=a*n%m}if n0;b=b*b%m;n/=2)while n>0 end p a }