It's Showtime!

Akane

Players can play games against the game machines!

Each machine is configured with a positive integer $N$ of at least $1$, a positive integer $a$ not exceeding $N$, and a character $b$ representing an operator. The operator $b$ is either $+$ or $\times$!

Each machine reveals $N$, but not $a$ or the operator $b$. A player may enter an integer from $1$ to $N$, inclusive. Each time the player enters an integer, the machine displays Yes or No according to the following internal procedure.

• Let $x$ be the value stored inside the machine. Initially, $x = a$.

• In each round, the player may enter an integer.

  • Let the entered integer be $y$, which must be between $1$ and $N$, inclusive.

  • If applying operator $$ to the stored value and the entered integer produces a value at most , the machine displays Yes; otherwise, it displays No. In other words, letting :

The player's goal is to identify operator $b$; there is no need to determine $a$. Once the player identifies $b$, fewer rounds mean more currency earned.

While wandering around the ship, Asuna happened to pick up a note listing information about every game machine. The note specifies the $a$ and $b$ configured for each machine.

Asuna thinks that guessing $b$ immediately might arouse the casino's suspicion and get her thrown out, so she wants to play the minimum number of rounds needed to avoid suspicion.

The integers Asuna has entered so far, together with the Yes/No response to each, form a transcript. Consider whether there is a pair $(a', b')$ that could produce exactly the same Yes/No responses for those inputs.

• If the transcript is impossible with $b'=+$ for every choice of $a'$, and is possible only with $b'=\times$, then she can conclude that .

Thus, as soon as only one operator remains possible, she can give the correct answer without arousing suspicion. Given a machine configured with $N$, $a$, and $b$, find the minimum number of rounds after which Asuna can answer correctly without arousing suspicion.

The character $\texttt{*}$ in the input represents $\times$.

The second game machine

• Entering $1$ in the first round displays Yes.

  • The possible pairs $(a, b)$ are $(1, \times)$, $(2, \times)$, $(3, \times)$, $(1, +)$, $(2, +)$, so the operator cannot yet be determined.

• Entering $1$ in the second round displays Yes.

  • The possible pairs $(a, b)$ are $(1, \times)$, $(2, \times)$, $$, , so the operator cannot yet be determined.

• Entering $1$ in the third round displays Yes.

  • The possible pairs $(a, b)$ are $(1, \times)$, $(2, \times)$, $$, so must be .

There is no way to determine $b$ with fewer than $3$ inputs.

• If $x'$ is greater than $N$, it displays No.
• If $x'$ is at most $N$, it displays Yes and updates $x$ to $x'$.

Time limit

1000 ms

Memory limit

1024 MB

Checker

CUSTOM