There is an island called PiLiPaLa.In the island there is a wild animal living in it, and you can call them PuPu. PuPu is a kind of special animal, infant PuPus play under the sunshine, and adult PuPus hunt near the seaside. They fell happy every day. 

But there is a question, when does an infant PuPu become an adult PuPu? 
Aha, we already said, PuPu is a special animal. There are several skins wraping PuPu's body, and PuPu's skins are special also, they have two states, clarity and opacity. The opacity skin will become clarity skin if it absorbs sunlight a whole day, and sunshine can pass through the clarity skin and shine the inside skin; The clarity skin will become opacity, if it absorbs sunlight a whole day, and opacity skin will keep sunshine out. 

when an infant PuPu was born, all of its skins were opacity, and since the day that all of a PuPu's skins has been changed from opacity to clarity, PuPu is an adult PuPu. 

For example, a PuPu who has only 3 skins will become an adult PuPu after it born 5 days(What a pity! The little guy will sustain the pressure from life only 5 days old) 

Now give you the number of skins belongs to a new-laid PuPu, tell me how many days later it will become an adult PuPu?

Input

There are many testcase, each testcase only contains one integer N, the number of skins, process until N equals 0

Output

Maybe an infant PuPu with 20 skins need a million days to become an adult PuPu, so you should output the result mod N

Sample Input

2
3
0

Sample Output

1
2

题意：这个题的题意蛮有意思的 就是有一种生物 它有很多层皮肤 而且成年的标志是每一层皮肤都变透明过（注意不是同时透明，即最内层透明就可以了）

然后这种生物每天都会晒太阳 晒一天太阳 最外层的不透明皮肤就会变透明（阳光会穿过外层的透明皮肤），同时这一天阳光穿过的透明的皮肤又会变成不透明的 ，然后问你最内层透明的需要晒多少天太阳

题解：解法有两种 1.暴力打表 看一下规律 就会发现ans=2^(n-1)+1;

2.推理一下 设ans[n]为第n层透明的天数total[n]为前n层同时透明的天数

假如四层皮肤

第一天       第二天    第三天    第四天    第五天   第六天   第七天   第八天    第九天

    +                  -            +              -            +            -            +            -               +

    +                 +             -              -            +           +            -             -               +

    +                 +            +             +            -             -            -             -               +

    +                 +            +             +            +           +            +            +               -

首先第n层透明 首先要求前一天前n-1层同时透明 所以ans[n]=total[n-1]+1;

又因为 第n层全部透明 是第n天透明而且前n-1天同时透明 又根据上面的表格total[n]=ans[n]+total[n-1]-1；

合并两个方程解得total[n]=total[n-1]*2; total[1]=1;所以total[n]=2^n；

ans[n]=2^(n-1)+1;

思路借鉴了这里

#include <bits/stdc++.h>
#define maxn 1000+5
using namespace std;
typedef long long int ll;
int quick_powmod(ll a,ll b,ll m){
    a%m;
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return int(ans);
}
int main(){
    ll n;
    while(scanf("%lld",&n)&&n){
        ll ans=quick_powmod(2,n-1,n)+1;
        printf("%d\n",ans);
    }
    return 0;
}