This problem can be solved in an \(O(\sqrt{P}\log{P})\) time per test case with a method called baby-step giant-step.

What is baby-step giant-step?

Baby-step giant-step is a method to find, given \(f,x,y\), the minimum \(n\) such that \(f^n(x)=y\).
We answer this problem by, for an arbitrary constant \(M\), solving the problem “what is the minimum value of \(0\leq j< M\) such that \(f^{iM}(x)=(f^{-1})^j(y)\), if exists?”
If \(f^{-1}\), this subproblem can be rephrased to “what is the minimum value of \(0\leq j< M\) such that \(f^{iM}(x)=(f^{-1})^j(y)\), if exists?” The idea of this algorithm that, once we enumerate the candidates for the left hand side, we can determine the existence fast for each \(i\).

The solution for this problem

If \(A=0\), it is easy to find the answer. We consider when \(A\neq 0\). Here, if there is an \(n\) such that \(X_n=T\), then that is at most \(P\). Therefore, we consider applying baby-step giant-step with \(M=\lfloor\sqrt{P}\rfloor\).
The inverse function of \(f(x)=Ax+B\) can be explicitly found in the form \(f^{-1}(x)=Cx+D\), so we can find \(f^M\) explicitly in the form \(f^M(x)=A'x+B'\). Thus, by enumerating \(M\) values \(T,f^{-1}(T),f^{-1}(f^{-1}(T)),\ldots\) and checking if any of \(S,f^M(S),f^M(f^M(S)),\ldots\) coincides with them, in this order, so that the problem is solved in a total of \(O(M\log{M})\) time (or expected \(O(M)\) time using a hash map).
When implementing, beware of the cases where \(T,f^{-1}(T),f^{-1}(f^{-1}(T)),\ldots\) have duplicates when the sequence \((X_i)\) has a period less than \(M\). (In that case, the answer is \(M\) anyway, so one solution to search exhaustively for these candidates firsthand.)

Sample code (C++)
Sample code (Python)

Another solution

If \(A=1\), it is easy to find the answer. We consider when \(A\neq 1\). Let \(\alpha=\frac{B}{A-1}\) and \(Y_i=X_i+\alpha\), then we have \(Y_i=AY_{i-1}\), so \(Y_i=Y_0 A^i\). Thus the original problem is boiled down to a discrete logarithm problem, which can be solved in a total of \(O(\sqrt{P}\log{P})\) time (or expected \(O(\sqrt{P})\) time using a hash map).
This solution is by en_translator.

Bonus: solve for a non-prime \(P\) in an \(O(\sqrt{P}\log{P})\) time.