You have moved to a new town. As starting a new life, you have made up your mind to do one thing: lying about your age. Since no person in this town knows your history, you don’t have to worry about immediate exposure. Also, in order to ease your conscience somewhat, you have decided to claim ages that represent your real ages when interpreted as the base-M numbers (2 ≤ M ≤ 16). People will misunderstand your age as they interpret the claimed age as a decimal number (i.e. of the base 10).

Needless to say, you don’t want to have your real age revealed to the people in the future. So you should claim only one age each year, it should contain digits of decimal numbers (i.e. ‘0’ through ‘9’), and it should always be equal to or greater than that of the previous year (when interpreted as decimal).

How old can you claim you are, after some years?



Input

The input consists of multiple datasets. Each dataset is a single line that contains three integers A, B, and C, where A is the present real age (in decimal), B is the age you presently claim (which can be a non-decimal number), and C is the real age at which you are to find the age you will claim (in decimal). It is guaranteed that 0 ≤ A < C ≤ 200, while B may contain up to eight digits. No digits other than ‘0’ through ‘9’ appear in those numbers.

The end of input is indicated by A = B = C = -1, which should not be processed.

Output

For each dataset, print in a line the minimum age you can claim when you become C years old. In case the age you presently claim cannot be interpreted as your real age with the base from 2 through 16, print -1 instead.

Example

Input

23 18 53
46 30 47
-1 -1 -1


Output

49
-1
#include<stdio.h>
#include<algorithm>
using namespace std;
char str[20];
char s[20];
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),~a){
		bool ok=false;
		sprintf(str,"%d",b);
		for(int i=2;i<17;i++){
			long long tmp=0;
			for(int j=0;str[j];j++){
				tmp*=i;
				tmp+=str[j]-'0';
			}
			bool OK=true;
			for(int j=0;str[j];j++){
				if(str[j]-'0'>=i)OK=false;
			}
			if(tmp==a&&OK)ok=true;
		}
		if(!ok){
			printf("-1\n");continue;
		}
		for(int i=a+1;i<=c;i++){
			int to=999999999;
			for(int j=2;j<17;j++){
				int tmp=i;
				int at=0;
				while(tmp){
					s[at++]='0'+tmp%j;
					tmp/=j;
				}
				ok=true;
				for(int k=0;k<at;k++){
					if(s[k]>'9')ok=false;
					str[at-1-k]=s[k];
				}
				if(ok){
					str[at]=0;
					int val;
					sscanf(str,"%d",&val);
					if(b<=val)to=min(to,val);
				}
			}
			b=to;
		}
		printf("%d\n",b);
	}
}