/*input
4
1
3
5
7
*/
#include <bits/stdc++.h>
using namespace std;
int step = 0;
int f(int x,int y){
	if(y != 0) step += x/y - (y==1); 
	if (y == 0) return x;
	return f(y,x%y);
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie();
	int test;cin>>test;
 	while (test--){
		int n;cin>>n;
		int ans = n-1;
		for(int i=n/2;i<n;++i){
			step = 0;
			if (f(n,i) == 1){
				ans = min (ans , step);
			}
		}
		cout << ans << '\n';
	}
}