# Break RSA given a correct and faulty implementation

Suppose I have two machines, $A$ and $B$. $A$ encrypts a message $m$ and outputs the ciphertext $m^e \pmod n$. $B$ outputs $c$ such that $c = m^e \pmod p$ and $c = m^e + 1 \pmod q$. How can I use $A$ and $B$ to find $p$ and $q$? I am allowed to choose $m$ and $n$.

-
HINT $\$ Consider $\rm\ gcd(A(m)-B(m),\:pq)$