25180번 - 썸 팰린드롬

문제

재혁이는 최근에 두람이와 썸을 타기 시작했다. 어느 날 재혁이가 귀찮아진 두람이는 재혁이에게 말했다.

"내가 정수 $N$을 줄 테니 각 자릿수의 합(sum)이 $N$이 되는 썸 팰린드롬 수의 최소 자릿수를 구하면 썸 타줄게"

팰린드롬 수는 앞으로 읽어도, 뒤로 읽어도 같은 수이다. 예를 들어 1231ドル$은 팰린드롬 수가 아니고, 2112ドル$는 앞으로 읽어도, 뒤로 읽어도 같은 수이기 때문에 팰린드롬 수이다.

썸 팰린드롬 수는 팰린드롬 수의 조건을 만족하면서 각 자리 숫자의 합이 $N$이 되는 수이다.

예를 들어 $N$이 15ドル$라면 재혁이가 만들 수 있는 썸 팰린드롬 수는 42324ドル$가 있다. 하지만, 555ドル$도 만들 수 있기 때문에 썸 팰린드롬의 최소 자릿수는 3ドル$이다.

외로운 재혁이를 도와주자.

입력

첫째 줄에 각 자리수의 합이 되는 정수 $N$(1ドル \le N \le 10^9$)이 주어진다.

출력

첫째 줄에 재혁이가 만들 수 있는 팰린드롬 수의 최소 자릿수를 출력한다.

제한

힌트