Coppie che massimizzano i passi di Euclide fino a 50

Considera tutte le coppie di interi $(a, b)$ con $1 \le b < a \le 50$. L'algoritmo di Euclide calcola $\text{MCD}(a,b)$ sostituendo ripetutamente $(a,b)$ con $(b, a \bmod b)$ finché $b$ non diventa $0$; ogni sostituzione conta come un passo. Sia $M$ il numero massimo di passi che l'algoritmo può impiegare per una coppia in questo intervallo. Per quante coppie $(a,b)$ dell'intervallo l'algoritmo impiega esattamente $M$ passi?