Guess the Prime!

**This is an interactive problem.** Shef chose some prime number $P$ between $2$ and $10^9$ inclusive. You want to guess it. Before that, you may ask Shef at most $M$ questions, since he is quite busy. In each question, you tell Shef an integer $x$ ($1 \le x \le 10^9$) and Shef tells you $x^2$ modulo $P$. At the end, you guess Shef's prime $P$ and he tells you if your guess was correct. However