Coppie con esattamente 6 passi di Euclide fino a 100

Considera tutte le coppie di interi $(a,b)$ con $1 \le b < a \le 100$. 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. Per quante coppie $(a,b)$ dell'intervallo l'algoritmo impiega esattamente $6$ passi (né di più né di meno)?