멀린 숨기기

전쟁이 끝나 간다. 아서 왕과 충성스러운 신하들은 모드레드와 그의 수하들을 없애기 위해 뭉쳤다. 모든 일이 잘 풀리면 전쟁은 내일이면 끝난다. 이제 아서 왕을 걱정하게 하는 것은 암살자가 멀린을 노리고 있다는 소식뿐이다.

아서 왕은 멀린을 캄란의 10억 채의 집 중 한 곳에 숨기기로 했다. 캄란의 집에는 1, 2, . . . , 999 999 999, 1 000 000 000번이 붙어 있다. 아서 왕은 멀린을 어느 집에 숨겼는지 잊지 않기 위해 그것을 적어 두고 싶다. 그러나 보안이 걱정되어 집 번호를 암호화하려고 한다. 서기 5세기이므로 그가 쓸 암호화 방식은 아주 원시적이다. 먼저 번호를 양의 제곱수들의 합으로 적고, 그 제곱수들을 이어 붙여 그 문자열을 적는다.

예를 들어 집 번호가 46이면 46 = 36 + 9+ 1 = 62 + 32 + 12이므로 3691을 적을 수 있다. 아서 왕은 1369 (46 = 1 + 36 + 9)나 1619416 (46 = 16 + 1 + 9 + 4 + 16)을 적을 수도 있다. 아서 왕은 각 제곱수를 앞에 0이 오지 않게 적는다.

아서 왕이 적어 둔 암호화된 집 번호와 일치하는 캄란의 가장 작은 집 번호는 무엇인가?

입력은 한 줄이며, 암호화된 집 번호인 문자열이 주어진다. 암호화된 집 번호는 숫자 (0, 1, . . . , 9)로만 이루어져 있고 길이는 1 이상 100 000 이하이다.

암호화된 집 번호와 일치하는 캄란의 가장 작은 집 번호를 출력한다. 암호화된 집 번호가 아서 왕의 암호화 방식으로는 나올 수 없는 것이면 대신 -1을 출력한다.