import java.math.BigInteger;

public class Euler958 {

    static class InvResult {
        boolean ok;
        long inv;

        InvResult(boolean ok, long inv) {
            this.ok = ok;
            this.inv = inv;
        }
    }

    static InvResult modInvInRange(long a, long m) {
        a %= m;
        if (a < 0)
            a += m;
        long x = a;
        long y = m;
        long vx = 1;
        long vy = 0;
        while (x != 0) {
            long k = y / x;
            y %= x;
            vy -= k * vx;
            long tempX = x;
            x = y;
            y = tempX;
            long tempVx = vx;
            vx = vy;
            vy = tempVx;
        }
        if (y != 1)
            return new InvResult(false, 0);
        long inv = (vy < 0) ? (vy + m) : vy;
        return new InvResult(true, inv);
    }

    static class Ans {
        int steps;
        long val;

        Ans(int steps, long val) {
            this.steps = steps;
            this.val = val;
        }
    }

    static long solveF(long n) {
        for (int steps = 0;; ++steps) {
            Ans ans = new Ans(steps, n + 1);
            int d = (steps + 1) / 2;

            dfs(0, 1, 0, n, 0, steps, d, n, ans);

            if (ans.val <= n)
                return ans.val;
        }
    }

    static void dfs(long a, long b, long ca, long cb, int curDepth, int steps, int d, long n, Ans ans) {
        if (a > b) {
            long tempA = a;
            a = b;
            b = tempA;
            long tempCa = ca;
            ca = cb;
            cb = tempCa;
        }

        if (cb < 0)
            return;
        if (ca < 0) {
            long k = (-ca + b - 1) / b;
            ca += k * b;
            cb -= k * a;
            if (cb < 0)
                return;
        }
        if (a * ca + b * cb != n)
            return;

        if (curDepth == d) {
            long localA = a;
            long localB = b;
            long localCa = ca;
            long localCb = cb;

            if ((steps & 1) != 0) {
                localA *= 2;
                localB *= 2;
                localCa *= 2;
                localCb *= 2;
                localB -= localA / 2;
                localCa += localCb / 2;
                if (localA * localCa + localB * localCb != 4 * n)
                    return;
            }

            BigInteger norm = BigInteger.valueOf(localA).multiply(BigInteger.valueOf(localA))
                    .add(BigInteger.valueOf(localB).multiply(BigInteger.valueOf(localB)));
            if (norm.compareTo(BigInteger.valueOf(n)) < 0)
                return;

            BigInteger cross = BigInteger.valueOf(localCa).multiply(BigInteger.valueOf(localB))
                    .subtract(BigInteger.valueOf(localCb).multiply(BigInteger.valueOf(localA)));

            BigInteger k = cross.divide(norm);
            localCa -= k.longValue() * localB;
            localCb += k.longValue() * localA;
            cross = cross.subtract(k.multiply(norm));

            if (cross.compareTo(BigInteger.ZERO) < 0) {
                localCa += localB;
                localCb -= localA;
                cross = cross.add(norm);
            }

            check(localCa, localCb, localA, localB, norm, steps, d, n, ans, curDepth);
            localCa -= localB;
            localCb += localA;
            check(localCa, localCb, localA, localB, norm, steps, d, n, ans, curDepth);
            return;
        }

        long x = a;
        long y = b;
        for (int z = curDepth; z < steps / 2; ++z) {
            if (x > y) {
                long temp = x;
                x = y;
                y = temp;
            }
            x += y;
            long temp = x;
            x = y;
            y = temp;
        }
        if (x > y) {
            long temp = x;
            x = y;
            y = temp;
        }

        if ((steps & 1) != 0) {
            BigInteger y2 = BigInteger.valueOf(y).multiply(BigInteger.valueOf(y));
            BigInteger xy = BigInteger.valueOf(x).multiply(BigInteger.valueOf(y));
            BigInteger x2 = BigInteger.valueOf(x).multiply(BigInteger.valueOf(x));
            BigInteger sum = y2.multiply(BigInteger.valueOf(5)).divide(BigInteger.valueOf(4))
                    .add(xy).add(x2);
            if (sum.compareTo(BigInteger.valueOf(n)) < 0) {
                return;
            }
        } else {
            BigInteger x2 = BigInteger.valueOf(x).multiply(BigInteger.valueOf(x));
            BigInteger y2 = BigInteger.valueOf(y).multiply(BigInteger.valueOf(y));
            if (x2.add(y2).compareTo(BigInteger.valueOf(n)) < 0) {
                return;
            }
        }

        dfs(b, a + b, cb - ca, ca, curDepth + 1, steps, d, n, ans);
        if (0 < a && a < b) {
            dfs(a, a + b, ca - cb, cb, curDepth + 1, steps, d, n, ans);
        }
    }

    static void check(long cA, long cB, long localA, long localB, BigInteger norm, int steps, int d, long n, Ans ans,
            int curDepth) {
        if (cA < 0 || cB < 0)
            return;
        BigInteger ca2 = BigInteger.valueOf(cA).multiply(BigInteger.valueOf(cA));
        BigInteger cb2 = BigInteger.valueOf(cB).multiply(BigInteger.valueOf(cB));
        if (ca2.add(cb2).compareTo(norm) > 0)
            return;

        long x = cA;
        long y = cB;
        long vx = localA;
        long vy = localB;

        if ((steps & 1) != 0) {
            if ((vx & 1) != 0)
                return;
            if ((y & 1) != 0)
                return;
            x -= y / 2;
            vy += vx / 2;
            if ((vy & 1) != 0)
                return;
            if ((x & 1) != 0)
                return;
            x /= 2;
            y /= 2;
            vx /= 2;
            vy /= 2;
        }

        if (x * vx + y * vy != n)
            return;
        int ops = 0;
        for (; ops <= steps - d && x != 0 && y != 0; ++ops) {
            if (x > y) {
                long tempX = x;
                x = y;
                y = tempX;
                long tempVx = vx;
                vx = vy;
                vy = tempVx;
            }
            y -= x;
            vx += vy;
        }
        if (ops > steps - d)
            return;

        long o = vx + vy - n;
        o %= n;
        if (o < 0)
            o += n;

        InvResult invRes = modInvInRange(o, n);
        if (!invRes.ok)
            return;

        int newSteps = curDepth + ops;
        long minVal = Math.min(Math.min(o, n - o), Math.min(invRes.inv, n - invRes.inv));

        if (newSteps < ans.steps || (newSteps == ans.steps && minVal < ans.val)) {
            ans.steps = newSteps;
            ans.val = minVal;
        }
    }

    public static String solve() {
        return Long.toString(solveF(1000000000039L));
    }

    public static void main(String[] args) {
        if (solveF(7) != 2 || solveF(89) != 34 || solveF(8191) != 1856) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}