a,b=gets.split.map &:to_i
g=a.gcd b
gets;p $<.count{|e|x,y=e.split.map &:to_i;x%g==0&&y%g==0}