The Amazing Race 1

Problem contributed by @celonymire

A new season of The Amazing Race began, and selected participants can earn luxurious vacations while solving puzzles around the world... Will you cross the final line and earn the ultimate prize?

- The Amazing Race Productions

---

This is an interactive problem.

Sam has passed the audition phase and is officially competing in the race. The production team gave the green light and the race has officially started! After following their initial clue, they encounter a man that withholds their next clue unless they solve his puzzle! With Sam being a puzzle solver, he steps up to the challenge and interacts with the mysterious man...

The man has a secret number $X$ and you have to guess it with only one attempt. Before you finalize your answer, you can ask him a number $Y$ and he will answer if $Y$ divides into $X$. Due to the production timeline, you can only ask him $10^6$ times! Otherwise, the show gets delayed and you may risk automatic elimination.

The final answer does not count towards the number of times you ask him!

---

Task

Implement the function solve(man) that finds the secret number using the provided API.

• man is an object of type MysteriousMan, which is a namespace that provides the APIs to ask and answer.
• You will be using the provided API instead of communicating via standard input and output.

---

Provided API

man.ask(Y)

• Returns true if $Y$ divides $X$, otherwise false.
• You can call this function at most $10^6$ times.

man.answer(Y)

• Submit your guess $Y$.
• You can only call this function once.
• This call does not count towards the query limit.