Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all $m<n$ by brute force)? For simplicity, restrict to $m$ relatively prime to $n$. For example, if $n=13$ and we want 1 step, then $m=6$ works: $13=2\cdot6+1$. And for 3 steps $m=7$ works: $13=1\cdot7+5$, $7=1\cdot5+2$, and $5=2\cdot2+1$.

Since the algorithm is used to find the modular inverse $m^{-1}$ (mod $n$) the fewer steps it takes the easier it is to find (so in particular few step runs are convenient for making homework problems ☺). Note that it is easy to find pairs for a given length of the algorithm. Since the continued fraction of $n/m=[q_0;q_1,\dots,q_k]$ records the quotients one can take an arbitrary continued fraction of given length, and find $n,m$ by contracting it. Hence an alternative way to ask the question is if there is an efficient way to “parametrize” all continued fractions with a given numerator.

If the general question is too hard, what can be said for $n$ prime, and/or small lengths like 2,3,4? It is easy for 1, since $n=q\cdot m+1$ the requisite $m$ are just the divisors of $n-1$. But already for 2 we have to find $m,r$ that simultaneously satisfy $m|(n-r)$ and $r|(m-1)$, which does not look obvious how to do.

As you have mentioned:

an alternative way to ask the question is if there is an efficient way to “parametrize” all continued fractions with a given numerator.

I think this result can be of some help to your question.

I am not sure how is it directly related to the question. Maybe some users can point out in the comments section.