Gems in the maze

Scrooge McDuck has a new plan to increase his wealth. He found ancient ruins with an extraordinary maze. The maze consists of $n$ chambers numbered $0$ through $n - 1$. Each chamber contains exactly one gem. Chambers are connected by one-way tunnels. Each chamber has exactly two outgoing tunnels: one leads to the chamber numbered $(a \cdot v^2 + b \cdot v + c) \bmod n$, and the other brings you out of the maze.

You can enter the maze at any chamber, move along the tunnels, and collect the gems. Once you leave the maze, the self-destruct mechanism triggers, the ceiling collapses, and every gem you did not collect is lost forever.

Scrooge wants to know the maximum number of gems he can take from the maze.

The first line of the input contains four integers $a$, $b$, $c$, and $n$, which describe one particular maze.

Output a single line containing one integer: the maximum number of gems that can be taken from the maze.

The starting chamber matters. For instance, in the first test case Scrooge starts in chamber $0$. His only two options are a tunnel that leads back to chamber $0$ and a tunnel that leads outside, which is not much of a choice. A much better strategy is to start in chamber $2$ and follow the path $2 \rightarrow 8 \rightarrow 16 \rightarrow 32 \rightarrow 0 \rightarrow$ outside.