//CodeChef - FLAASH
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_INT = 2147483647;
int memo[1000050];
int race(int pos, int move)
{
if (pos < 1)
return MAX_INT;
if (pos == 1)
return move;
if (memo[pos] > -1)
return memo[pos];
return min(
race(pos - 1, move + 1),
min((pos % 2 == 0 ? race(pos / 2, move + 1) : MAX_INT),
(pos % 3 == 0 ? race(pos / 3, move + 1) : MAX_INT)));
}
int main()
{
int t;
cin >> t;
memset(memo, -1, sizeof(memo));
while (t--)
{
int n;
cin >> n;
cout << race(n, 0) << endl;
}
return 0;
}
Ly9Db2RlQ2hlZiAtIEZMQUFTSAojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RyaW5nPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE1BWF9JTlQgPSAyMTQ3NDgzNjQ3OwppbnQgbWVtb1sxMDAwMDUwXTsKCmludCByYWNlKGludCBwb3MsIGludCBtb3ZlKQp7CiAgaWYgKHBvcyA8IDEpCiAgICByZXR1cm4gTUFYX0lOVDsKICBpZiAocG9zID09IDEpCiAgICByZXR1cm4gbW92ZTsKICBpZiAobWVtb1twb3NdID4gLTEpCiAgICByZXR1cm4gbWVtb1twb3NdOwoKICByZXR1cm4gbWluKAogICAgICByYWNlKHBvcyAtIDEsIG1vdmUgKyAxKSwKICAgICAgbWluKChwb3MgJSAyID09IDAgPyByYWNlKHBvcyAvIDIsIG1vdmUgKyAxKSA6IE1BWF9JTlQpLAogICAgICAgICAgKHBvcyAlIDMgPT0gMCA/IHJhY2UocG9zIC8gMywgbW92ZSArIDEpIDogTUFYX0lOVCkpKTsKfQoKaW50IG1haW4oKQp7CiAgaW50IHQ7CiAgY2luID4+IHQ7CgogIG1lbXNldChtZW1vLCAtMSwgc2l6ZW9mKG1lbW8pKTsKICB3aGlsZSAodC0tKQogIHsKICAgIGludCBuOwogICAgY2luID4+IG47CiAgICBjb3V0IDw8IHJhY2UobiwgMCkgPDwgZW5kbDsKICB9CgogIHJldHVybiAwOwp9