시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB310997038.889%

문제

1827은 흥미로운 수이다. 그 이유는 1827=21*87이고, 좌변과 우변에 나온 숫자가 모두 같기 때문이다. 또, 136948도 비슷한 성질을 가지고 있다. 136948=146*938

위에서 설명한 숫자를 뱀파이어 숫자라고 한다. 즉, v가 뱀파이어 숫자가 되려면, 두 수 a와 b의 곱(v=a*b)으로 나타낼 수 있어야 하고, a와 b에 등장하는 숫자와 v와 같아야 한다. 또, a와 b의 자리수도 같아야 한다. v, a, b는 0으로 시작할 수 없다.

a와 b의 길이가 같아야 하기 때문에, v는 짝수 자리이어야 하지만, 이 문제에서는 a와 b의 길이가 다른 것도 뱀파이어 숫자라고 한다.

아래는 뱀파이어 숫자의 예이다.

126 = 6*21

10251 = 51*201

702189 = 9*78021

29632 = 32*926

숫자 X가 주어졌을 때, X보다 크거나 같은 뱀파이어 숫자 중 가장 작은 수를 찾는 프로그램을 작성하시오.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 정수 X(10 ≤ X ≤ 1,000,000)를 포함하는 한 줄로 이루어져 있다. 입력은 0이 있는 줄에서 끝난다.

출력

각각의 테스트 케이스에 대해서, X보다 크거나 같은 뱀파이어 숫자 중 가장 작은 작은 수를 출력한다.

예제 입력 1

10
126
127
5000
0

예제 출력 1

126
126
153
6880

힌트

뱀파이어 숫자는 실제로 있는 수이다. (위키)

W3sicHJvYmxlbV9pZCI6IjQwOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjNDBcdWQzMGNcdWM3NzRcdWM1YjQgXHVjMjJiXHVjNzkwIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0MTgyN1x1Yzc0MCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNzc0XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IDE4Mjc9MjEqODdcdWM3NzRcdWFjZTAsIFx1Yzg4Y1x1YmNjMFx1YWNmYyBcdWM2YjBcdWJjYzBcdWM1ZDAgXHViMDk4XHVjNjI4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWJhYThcdWI0NTAgXHVhYzE5XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCAxMzY5NDhcdWIzYzQgXHViZTQ0XHVjMmI3XHVkNTVjIFx1YzEzMVx1YzljOFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiAxMzY5NDg9MTQ2KjkzODxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJjNDBcdWQzMGNcdWM3NzRcdWM1YjQgXHVjMjJiXHVjNzkwXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCB2XHVhYzAwIFx1YmM0MFx1ZDMwY1x1Yzc3NFx1YzViNCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViNDE4XHViODI0XHViYTc0LCBcdWI0NTAgXHVjMjE4IGFcdWM2NDAgYlx1Yzc1OCBcdWFjZjEodj1hKmIpXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgYVx1YzY0MCBiXHVjNWQwIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM2NDAgdlx1YzY0MCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIGFcdWM2NDAgYlx1Yzc1OCBcdWM3OTBcdWI5YWNcdWMyMThcdWIzYzQgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gdiwgYSwgYlx1YjI5NCAwXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRhXHVjNjQwIGJcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCB2XHViMjk0IFx1YzlkZFx1YzIxOCBcdWM3OTBcdWI5YWNcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IGFcdWM2NDAgYlx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViMmU0XHViOTc4IFx1YWM4M1x1YjNjNCBcdWJjNDBcdWQzMGNcdWM3NzRcdWM1YjQgXHVjMjJiXHVjNzkwXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNTQ0XHViNzk4XHViMjk0IFx1YmM0MFx1ZDMwY1x1Yzc3NFx1YzViNCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxMjYgPSA2KjIxPFwvcD5cclxuPHA+XHJcblx0MTAyNTEgPSA1MSoyMDE8XC9wPlxyXG48cD5cclxuXHQ3MDIxODkgPSA5Kjc4MDIxPFwvcD5cclxuPHA+XHJcblx0Mjk2MzIgPSAzMio5MjY8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMjJiXHVjNzkwIFhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgWFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YmM0MFx1ZDMwY1x1Yzc3NFx1YzViNCBcdWMyMmJcdWM3OTAgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzgxNVx1YzIxOCBYKDEwICZsZTsgWCAmbGU7IDEsMDAwLDAwMClcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzQwIDBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzkwNFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBYXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHViYzQwXHVkMzBjXHVjNzc0XHVjNWI0IFx1YzIyYlx1Yzc5MCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM3OTFcdWM3NDAgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0XHViYzQwXHVkMzBjXHVjNzc0XHVjNWI0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWMyZTRcdWM4MWNcdWI4NWMgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC4gKDxhIGhyZWY9XCJodHRwOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9WYW1waXJlX251bWJlclwiPlx1YzcwNFx1ZDBhNDxcL2E+KTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDA5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZhbXBpcmUgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG51bWJlciAxODI3IGlzIGFuIGludGVyZXN0aW5nIG51bWJlciwgYmVjYXVzZSAxODI3PTIxKjg3LCBhbmQgYWxsIG9mIHRoZSBzYW1lIGRpZ2l0cyBhcHBlYXIgb24gYm90aCBzaWRlcyBvZiB0aGUgJmxzcXVvOz0mcnNxdW87LiBUaGUgbnVtYmVyIDEzNjk0OCBoYXMgdGhlIHNhbWUgcHJvcGVydHk6IDEzNjk0OD0xNDYqOTM4LiZuYnNwOzxcL3A+XHJcblxyXG48cD5TdWNoIG51bWJlcnMgYXJlIGNhbGxlZCBWYW1waXJlIE51bWJlcnMuIE1vcmUgcHJlY2lzZWx5LCBhIG51bWJlciB2IGlzIGEgVmFtcGlyZSBOdW1iZXIgaWYgaXQgaGFzIGEgcGFpciBvZiBmYWN0b3JzLCBhIGFuZCBiLCB3aGVyZSBhKmI9diwgYW5kIHRvZ2V0aGVyLCBhYW5kIGIgaGF2ZSBleGFjdGx5IHRoZSBzYW1lIGRpZ2l0cywgaW4gZXhhY3RseSB0aGUgc2FtZSBxdWFudGl0aWVzLCBhcyB2LiBOb25lIG9mIHRoZSBudW1iZXJzIHYsIGEgb3IgYiBjYW4gaGF2ZSBsZWFkaW5nIHplcm9zLiBUaGUgbWF0aGVtYXRpY2FsIGRlZmluaXRpb24gc2F5cyB0aGF0IHYgc2hvdWxkIGhhdmUgYW4gZXZlbiBudW1iZXIgb2YgZGlnaXRzIGFuZCB0aGF0IGEgYW5kIGIgc2hvdWxkIGhhdmUgdGhlIHNhbWUgbnVtYmVyIG9mIGRpZ2l0cywgYnV0IGZvciB0aGUgcHVycG9zZXMgb2YgdGhpcyBwcm9ibGVtLCB3ZSZyc3F1bztsbCByZWxheCB0aGF0IHJlcXVpcmVtZW50LCBhbmQgYWxsb3cgYSBhbmQgYiB0byBoYXZlIGRpZmZlcmluZyBudW1iZXJzIG9mIGRpZ2l0cywgYW5kIHYgdG8gaGF2ZSBhbnkgbnVtYmVyIG9mIGRpZ2l0cy4gSGVyZSBhcmUgc29tZSBtb3JlIGV4YW1wbGVzOjxcL3A+XHJcblxyXG48cD4xMjYgPSA2ICogMjE8YnIgXC8+XHJcbjEwMjUxID0gNTEgKiAyMDE8YnIgXC8+XHJcbjcwMjE4OSA9IDkgKiA3ODAyMTxiciBcLz5cclxuMjk2MzIgPSAzMiAqIDkyNjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIG51bWJlciBYLCBmaW5kIHRoZSBzbWFsbGVzdCBWYW1waXJlIE51bWJlciB3aGljaCBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gWC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIFggKDEwICZsZTsgWCAmbGU7IDEsMDAwLDAwMCkuIFRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciBvbiBpdHMgb3duIGxpbmUsIHdoaWNoIGlzIHRoZSBzbWFsbGVzdCBWYW1waXJlIE51bWJlciB3aGljaCBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gWC4gT3V0cHV0IG5vIGV4dHJhIHNwYWNlcywgYW5kIGRvIG5vdCBzZXBhcmF0ZSBhbnN3ZXJzIHdpdGggYmxhbmsgbGluZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==