나머지를 만들어요

이 문제는 인터랙티브 문제입니다.

호반우는 $10^{9}$ 이하의 음이 아닌 정수 $N$과 양의 정수 $M$을 가지고 있는데 $N$과 $M$이 무엇인지 궁금해하는 상호에게 다음과 같은 제안을 했다.

"$10^{9}$이하의 양의 정수 $X$를 고르면 $X$의 배수와 $N$과의 차이 중에서 가장 작은 값을 $M$으로 나눈 나머지를 알려줄게. 단, 질문은 최대 $100$번까지 할 수 있어."

호반우는 상호가 예측한 $N, M$이 자신이 가진 $N, M$과 달라도 $10^{9}$ 이하의 모든 양의 정수 $X$에 대한 질문에서 대답이 일치한다면 정답으로 인정하려 한다.

상호가 $N, M$으로 예측한 수가 $A, B$이고 호반우가 이를 정답으로 인정했을 때 가능한 $A, B$ 중에서 $A + B$가 가장 작은 걸 찾아보자.