ISL 2022 N3

Let $a>1$ be a positive integer, and let $d>1$ be a positive integer coprime to $a$. Let $x_{1}=1$ and, for $k \geqslant 1$, define $$x_{k+1}= \begin{cases}x_{k}+d & \text { if } a \text { doesn't divide } x_{k} \\ x_{k} / a & \text { if } a \text { divides } x_{k}\end{cases}$$ Find the greatest positive integer $n$ for which there exists an index $k$ such that $x_{k}$ is divisible by $a^{n}$. (Croatia)