Below is an old olympiad problem, that turned out to be notoriously hard, that we couldn't solve it. If anyone has a solution for it, I'd be grateful.

Let $P(x)=x+1$, and $Q(x)=x^2+1$. We consider all sequences of pairs, namely, $\{(x_k,y_k)\}_{k=1}^\infty$ such that, we have the following rule to generate: $(x_1,y_1)=(1,3)$, and for every $k$, $(x_{k+1},y_{k+1})$ is, $$ \text{either } (P(x_k),Q(y_k)) \text{ or } (Q(x_k),P(y_k)). $$ Call a positive integer $n$ as cute, if there exists at least one such sequence, on which, $x_n=y_n$. Find all cute $n$'s.