Example

Input

3


Output

1
#include<iostream>
#include<algorithm>
using namespace std;
long N;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
long power(long a,long b,long mod){return b?power(a*a%mod,b/2,mod)*(b%2?a:1)%mod:1;}
int phi(int N)
{
	int ret=N;
	for(int i=2;i*i<=N;i++)
	{
		if(N%i==0)
		{
			while(N%i==0)N/=i;
			ret=ret/i*(i-1);
		}
	}
	if(N>1)ret=ret/N*(N-1);
	return ret;
}
int main()
{
	cin>>N;
	if(N==2)
	{
		cout<<1<<endl;
		return 0;
	}
	int tN=N;
	int L=1;
	for(int i=2;i*i<=tN;i++)
	{
		if(tN%i==0)
		{
			tN/=i;
			if(tN%i==0)
			{
				cout<<-1<<endl;
				return 0;
			}
			L=L/gcd(L,i-1)*(i-1);
		}
	}
	if(tN>1)
	{
		L=L/gcd(L,tN-1)*(tN-1);
	}
	int nl=phi(L);
	int ans=nl+1;
	for(int i=1;i*i<=nl;i++)
	{
		if(nl%i==0)
		{
			if(power(N,i,L)==1)ans=min(ans,i);
			if(power(N,nl/i,L)==1)ans=min(ans,nl/i);
		}
	}
	cout<<(ans>nl?-1:ans)<<endl;
}
