In their 2015 paper "More Rounds, Less Security?" Guo, Jean, Mouha and Nikolić claim in section 5.4 that one can recover a password $P$ given hashes of $D$ different passwords generated from $H^k(P)$ with about $T_1=\frac{2^n}{D\cdot k}$ hash evaluations.
Now I understand that using standard preimage search you are expected to find at least one preimage in $2^n/D$ evaluations of the full iterated hash, so $T_2=\frac{k\cdot 2^n}{D}$ hash evaluations.
The reasoning given for $T_1$ is:
Now observe that the time complexity can be reduced by a factor of $k$. This is because evaluating one password guess requires $k$ evaluations of the hash function used inside [the password hash], but every additional guess has an additional cost of only one hash function evaluation. This effectively speeds up exhaustive search by a factor of $k$: given $D$ password hashes, recovering any of them has a time complexity of $2^n/(D \cdot k)$.
My question is now (based on my current understanding of the above quote):
Given $H^{i}(P)$ for $i\in\{1,\ldots,k\}$ using only one evaluation of $H$ how does one compute $H^k(P')$ for any $P'\neq P$?
Or asked differently but (hopefully) equivalently:
How exactly does this pre-image search speedup trick work where additional checks after the initial evaluation only cost one hash evaluation?