На самом деле достаточно сделать $$$20$$$ запросов. Стоит вспомнить, что любое число представимо в двоичной записи. Нам известно, что младший (нулевой) бит числа равен $$$1$$$ ($$$p$$$ простое и $$$p \ge 3$$$). Попробуем угадать первый бит. Спросим, правда ли остаток от деления на $$$4$$$ равен $$$1$$$. При положительном ответе первый бит равен $$$0$$$, при отрицательном — $$$1$$$. Аналогично будем угадывать остальные биты по возрастанию, в качестве $$$d$$$ будем использовать уже построенное число. Поскольку $$$p \le 10^6 < 2^{20}$$$, за девятнадцать запросов мы спросим биты, соответствующие $$$2^1, 2^2, \ldots, 2^{19}$$$, а значит полностью восстановим число. Двадцатым запросом выведем ответ.