#!ruby -ropenssl
t = gets.to_i
t.times {
    a, pp = gets.split.map &:to_i
    if OpenSSL::BN.new(pp).prime? then
        p a-1
    else
        p -1
    end
}