#include<bits/stdc++.h>
using namespace std;
int N=100000;
long long Max= 1000000007;
int main()
{
long long x;
while(cin>>x)
{
queue<long long>q;
map<long long,int>m;
m[x]=1;
q.push(x);
int flag=0;
while(!q.empty())
{
long long a=q.front();
q.pop();
if(a==0)
{
cout<<m[a]-1<<endl;
flag=1;
break;
}
if(m[a]<=N)
{
if(!m[(a*4+3)%Max])
{
m[(a*4+3)%Max]=m[a]+1;
q.push((a*4+3)%Max);
}
if(!m[(a*8+7)%Max])
{
m[(a*8+7)%Max]=m[a]+1;
q.push((a*8+7)%Max);
}
}
}
if(flag==0)
cout<<"-1"<<endl;
}
return 0;
}
