#include <bits/stdc++.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int t;
int n;
int main(int argc, char** argv) {
	cin>>t;
	int a,b;
	int ans=0;
	for(int i=0;i<t;i++){
		cin>>n;
		a=0,b=n;
		while(a<=b){
			if(a!=0){
				a++;
			}
			if(__gcd(a,b)>1){
				a/=__gcd(a,b);
				b/=__gcd(a,b);
			}
			ans++;
		}
		cout<<ans<<endl;
		n=0,ans=0,a=0,b=0;
	}
	return 0;
}