You are given a positive integer n, written without leading zeroes (for example, the number 04 is incorrect). 

In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.

Determine the minimum number of operations that you need to consistently apply to the given integer n to make from it the square of some positive integer or report that it is impossible.

An integer x is the square of some positive integer if and only if x=y^2 for some positive integer y.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^{9}). The number is given without leading zeroes.

Output

If it is impossible to make the square of some positive integer from n, print -1. In the other case, print the minimal number of operations required to do it.

Examples

Input

8314


Output

2


Input

625


Output

0


Input

333


Output

-1

Note

In the first example we should delete from 8314 the digits 3 and 4. After that 8314 become equals to 81, which is the square of the integer 9.

In the second example the given 625 is the square of the integer 25, so you should not delete anything. 

In the third example it is impossible to make the square from 333, so the answer is -1.
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static InputReader in;
    static PrintWriter out;
    static long time_start;
    static int cas = 0;
    static int mod = (int) 12357;
    static int inf = 0x3f3f3f3f;
    static long inff = 0x3f3f3f3f3f3f3f3fL;
    static int maxn = (int) 1e8 + 5;

    static class Node {
        String n;
        int step;
        Node() {}
        Node(String n, int step) {
            this.n = n;
            this.step = step;
        }
    }


    static void solve() throws Exception {

        while (in.hasNext()) {
            String n = in.next();
            out.println(bfs(n));
        }
    }

    static int bfs(String n) {
        Queue<Node> que = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        que.offer(new Node(n, 0));
        set.add(Integer.valueOf(n));

        while (!que.isEmpty()) {
            Node u = que.poll();
            if (check(u)) {
                return u.step;
            }
            for (int i = 0; i < u.n.length(); ++i) {
                String ed = (i == u.n.length() - 1 ? "" : u.n.substring(i + 1));
                String st = (i == 0 ? "" : u.n.substring(0, i));
                String nstr = st + ed;
                if (!nstr.equals("") && nstr.charAt(0) != '0' && !set.contains(Integer.valueOf(nstr))) {
                    set.add(Integer.valueOf(nstr));
                    que.offer(new Node(nstr, u.step + 1));
                }
            }
        }
        return -1;
    }

    static boolean check(Node node) {
        int n = Integer.valueOf(node.n);
        int sn = (int)(Math.sqrt(n) + 1e-8);
        return sn * sn == n;
    }

    public static void main(String[] args) throws Exception {
        openIO();
        solve();
        closeIO();
    }

    static void openIO() throws Exception {
        try {
            time_start = 0;
            FileInputStream fi = new FileInputStream("night_input");
            System.setIn(fi);
            time_start = System.currentTimeMillis();
        } catch (Exception ex) {
            //hello night_13
        }

        in = new InputReader(System.in);
        out = new PrintWriter(new BufferedOutputStream(System.out));
    }

    static void closeIO() throws IOException {
        out.flush();

        if (time_start != 0) {
            out.println();
            out.print("time cost: ");
            out.print(System.currentTimeMillis() - time_start);
            out.println(" ms");
        }
        in.close();
        out.close();
    }
}


class InputReader {
    private BufferedReader br;
    private StringTokenizer st;

    public InputReader(InputStream stream) throws IOException {
        br = new BufferedReader(new InputStreamReader(stream));
        eat("");
    }

    private void eat(String s) {
        st = new StringTokenizer(s);
    }

    public String nextLine() throws IOException {
        return br.readLine();
    }

    public boolean hasNext() throws IOException {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null) return false;
            eat(s);
        }
        return true;
    }

    public String next() throws IOException {
        hasNext();
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextBigDecimal() throws IOException {
        return new BigDecimal(next());
    }

    public int[] nextIntArray(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextInt();
        }
        return arr;
    }

    public double[] nextDoubleArray(int n) throws IOException {
        double[] arr = new double[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextDouble();
        }
        return arr;
    }

    public char[] nextCharArray() throws IOException {
        return next().toCharArray();
    }

    public int[] nextIntArray(int n, int st) throws IOException {
        n += st;
        int[] arr = new int[n];
        for (int i = st; i < n; ++i) {
            arr[i] = nextInt();
        }
        return arr;
    }

    public double[] nextDoubleArray(int n, int st) throws IOException {
        n += st;
        double[] arr = new double[n];
        for (int i = st; i < n; ++i) {
            arr[i] = nextDouble();
        }
        return arr;
    }

    public char[] nextCharArray(int st) throws IOException {
        String temp = "";
        while (st-- > 0) temp += " ";
        return (temp + next()).toCharArray();
    }

    public void close() throws IOException {
        br.close();
    }
}

