#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int get(int num){
    if(num==1)return 0;
    else if(num&1)return (get(num/2)+1)*2%(num+1);
    else return (get(num/2)*2)%(num);
}
int main()
{
    //freopen("in.txt","r",stdin);
    char c[5];
    int a,b,d;
    while(scanf("%s",c)){
        a=c[0]-'0',b=c[1]-'0',d=c[3]-'0';
        if(a==0&&b==0&&d==0)break;
        int num=(a*10+b)*(int)pow(10,d*1.0);
        int ans=get(num)+1;
        cout<<ans<<endl;
    }
    return 0;
}