Let \(a > 1\) be a positive integer and \(d > 1\) be a positive integer coprime to \(a\). Let \(x_1=1\), and for \(k\geq 1\), define

\[x_{k+1} = \begin{cases} x_k + d &\text{if } a \text{ does not divide } x_k \\ x_k/a & \text{if } a \text{ divides } x_k \end{cases}\]

Find, in terms of \(a\) and \(d\), the greatest positive integer \(n\) for which there exists an index \(k\) such that \(x_k\) is divisible by \(a^n\).