#include <stdio.h>
#include <iostream>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL)
int main()
{
fastio;
int n,a,b,max,min,n2,T,i,count;
cin >> T;
for(i = 0 ; i < T ; i++) { count=0;
cin >> n;
min=n;
while(n!=0)
{ for(a=2;a<n;a++)
{ if(n%a==0)
{
b=n/a;
if(a>=b)
max=a;
else if (b>a)
max=b;
}
if(min>max)
min=max;
}
n2=n-1;
if(n2<min)
{n=n2;
count=count+1;
}
else
{
n=min;
count=count+1;
}
}
cout << count << endl;
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgojaW5jbHVkZSA8aW9zdHJlYW0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBmYXN0aW8gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IHN0ZDo6Y2luLnRpZShOVUxMKTsgc3RkOjpjb3V0LnRpZShOVUxMKQoKaW50IG1haW4oKQp7CiAgICBmYXN0aW87CiAgICAgaW50IG4sYSxiLG1heCxtaW4sbjIsVCxpLGNvdW50OwogIGNpbiA+PiBUOwogIGZvcihpID0gMCA7IGkgPCBUIDsgaSsrKSB7ICAgIGNvdW50PTA7CiAgICAgICBjaW4gPj4gbjsKICAgICAgIG1pbj1uOwogICAgICAgd2hpbGUobiE9MCkKICAgICAgIHsgZm9yKGE9MjthPG47YSsrKQogICAgICAgICAgICB7IGlmKG4lYT09MCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBiPW4vYTsKCiAgICAgICAgICAgICAgICAgICAgaWYoYT49YikKICAgICAgICAgICAgICAgICAgICAgICAgbWF4PWE7CiAgICAgICAgICAgICAgICAgICAgZWxzZSBpZiAoYj5hKQogICAgICAgICAgICAgICAgICAgICAgICBtYXg9YjsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAgICAgaWYobWluPm1heCkKICAgICAgICAgICAgICAgICAgICAgICAgbWluPW1heDsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgbjI9bi0xOwogICAgaWYobjI8bWluKQogICAgICAge249bjI7CiAgICAgICAgY291bnQ9Y291bnQrMTsKICAgICAgICB9CiAgICBlbHNlCiAgICAgICB7CiAgICAgICAgbj1taW47CiAgICAgICAgIGNvdW50PWNvdW50KzE7CiAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjb3V0IDw8IGNvdW50IDw8IGVuZGw7CiAgfQpyZXR1cm4gMDsKfQ==