Minimum Digit Sum for x with a Specified Square Digit Sum

Given a nonnegative integer \(y\), find the minimum possible digit sum of a nonnegative integer \(x\) that satisfies that the digit sum of \(x^2\) equals \(y\). The digit sum of an integer is defined as the sum of its decimal digits. Formally, for any nonnegative integer \(n\) with decimal representation \(n = \sum_{i=0}^{k} b_i \times 10^{i}\) (where \(0 \le b_i < 10\) and the representation is unique), the digit sum of \(n\) is defined as \(\sum_{i=0}^{k} b_i\).

If there is no such \(x\), output -1.

inputFormat

The input consists of a single nonnegative integer \(y\).

outputFormat

Output a single integer representing the minimum possible digit sum of \(x\), where \(x\) is a nonnegative integer satisfying that the digit sum of \(x^2\) equals \(y\). If no such \(x\) exists, output -1.

sample

0

0