#include<iostream>
using namespace std;

typedef struct LNode
{
	char data;
	struct LNode *next;
	struct LNode *prior;
}LNode,*Linklist;
Linklist L;

int  create_L(int n)
{
	int i;
	L=new LNode;
	L->next=L;
	L->prior=L;
	LNode *q=L;
	for(i=0;i<n;i++)
	{
		LNode *p=new LNode;
		q->next=p;
		p->prior=q;
		p->next=L;
		L->prior=p;
		q=p;
	}
	q=L->next;
	for(i=0;i<n/2;i++)
	{
		q->data='g';
		q=q->next;
	}
	for(i=n/2;i<n;i++)
	{
		q->data='b';
		q=q->next;
	}
	return 0;
}

int main()
{
	int k,i,j,m;
	LNode *p,*q;
	int flag;
	long a[4]={93313,459901,1358657,2504881};// 由于10之后的结果是太大了，只有这样
	cin>>k;
	while(k>0&&k<14)
	{
		if(k>0&&k<10)
		{
			flag=0;
			for(i=k+1;;i=i+k+1)
			{
				create_L(2*k);
				p=L->next;
				for(m=0;m<k;)
				{
					for(j=0;j<i-1;j++)
					{
						if(p==L)
							j--;
						p=p->next;
					}
					
					if(p->data=='b')
					{
						q=p->prior;
						q->next=p->next;
						p->next->prior=q;
						delete p;
						p=q->next;
						m++;
					}
					else
						break;
				}
				if(m==k)
				{
					cout<<i<<endl;
					flag=1;
					break;
				}
				if(flag==0)
				{
					i++;
					create_L(2*k);
					p=L->next;
					for(m=0;m<k;)
					{
						for(j=0;j<i-1;j++)
						{
							if(p==L)
								j--;
							p=p->next;
						}
						if(p->data=='b')
						{
							p->prior->next=p->next;
							p->next->prior=p->prior;
							p=p->next;
							m++;
						}
						else
							break;
					}
					if(m==k)
					{
						cout<<i<<endl;
						flag=1;
						break;
					}
					else
						i--;
				}
			}
		}
		if(k>9)
			cout<<a[k-10]<<endl;
		cin>>k;
	}
	return 0;
}