import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

public class Euler983 {
    static class Point implements Comparable<Point> {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) {
            if (this.x != o.x)
                return Integer.compare(this.x, o.x);
            return Integer.compare(this.y, o.y);
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Point))
                return false;
            Point p = (Point) obj;
            return x == p.x && y == p.y;
        }

        @Override
        public int hashCode() {
            return x * 31 + y;
        }
    }

    static long pairKey(int x, int y) {
        return (((long) x) << 32) ^ ((long) y & 0xFFFFFFFFL);
    }

    static List<Point> circlePoints(int m) {
        int r = (int) Math.sqrt(m);
        List<Point> pts = new ArrayList<>();
        for (int x = -r; x <= r; ++x) {
            int y2 = m - x * x;
            if (y2 < 0)
                continue;
            int y = (int) Math.sqrt(y2);
            if (y * y == y2) {
                pts.add(new Point(x, y));
                if (y != 0)
                    pts.add(new Point(x, -y));
            }
        }
        Collections.sort(pts);
        List<Point> unique = new ArrayList<>();
        for (Point p : pts) {
            if (unique.isEmpty() || !unique.get(unique.size() - 1).equals(p)) {
                unique.add(p);
            }
        }
        return unique;
    }

    static List<Point[]> oppositePairs(List<Point> points) {
        HashSet<Long> used = new HashSet<>();
        List<Point[]> pairs = new ArrayList<>();
        for (Point v : points) {
            long k = pairKey(v.x, v.y);
            if (used.contains(k))
                continue;
            Point ov = new Point(-v.x, -v.y);
            used.add(k);
            used.add(pairKey(ov.x, ov.y));
            pairs.add(new Point[] { v, ov });
        }
        return pairs;
    }

    static int oppositePairCountByFactorization(long m) {
        if (m == 0)
            return 0;
        long n = m;
        int pairs = 2;

        while ((n & 1) == 0)
            n >>= 1;

        for (long p = 3; p * p <= n; p += 2) {
            if (n % p != 0)
                continue;
            int exp = 0;
            while (n % p == 0) {
                n /= p;
                exp++;
            }
            if ((p & 3) == 3) {
                if ((exp & 1) != 0)
                    return 0;
            } else if ((p & 3) == 1) {
                pairs *= (exp + 1);
            }
        }

        if (n > 1) {
            if ((n & 3) == 3)
                return 0;
            if ((n & 3) == 1)
                pairs *= 2;
        }

        return pairs;
    }

    static HashSet<Long> buildBadDisplacements(List<Point> points) {
        HashSet<Long> bad = new HashSet<>();
        for (Point a : points) {
            for (Point b : points) {
                if (a.equals(b))
                    continue;
                bad.add(pairKey(a.x - b.x, a.y - b.y));
            }
        }
        return bad;
    }

    static boolean fourTupleHasForbiddenSum(Point[] selected, int usedCount, HashSet<Long> badDisp) {
        if (usedCount < 4)
            return false;
        Point d = selected[usedCount - 1];
        for (int i = 0; i < usedCount - 1; ++i) {
            Point a = selected[i];
            for (int j = i + 1; j < usedCount - 1; ++j) {
                Point b = selected[j];
                for (int k = j + 1; k < usedCount - 1; ++k) {
                    Point c = selected[k];
                    for (int mask = 0; mask < 16; ++mask) {
                        int sx = ((mask & 1) != 0 ? -a.x : a.x) +
                                ((mask & 2) != 0 ? -b.x : b.x) +
                                ((mask & 4) != 0 ? -c.x : c.x) +
                                ((mask & 8) != 0 ? -d.x : d.x);
                        int sy = ((mask & 1) != 0 ? -a.y : a.y) +
                                ((mask & 2) != 0 ? -b.y : b.y) +
                                ((mask & 4) != 0 ? -c.y : c.y) +
                                ((mask & 8) != 0 ? -d.y : d.y);
                        if (sx == 0 && sy == 0)
                            continue;
                        if (badDisp.contains(pairKey(sx, sy)))
                            return true;
                    }
                }
            }
        }
        return false;
    }

    static boolean testSelectedVectors(Point[] v, List<Point> lattice) {
        int d = v.length;
        int full = 1 << d;
        Point[] sums = new Point[full];
        sums[0] = new Point(0, 0);

        for (int mask = 1; mask < full; ++mask) {
            int bit = Integer.numberOfTrailingZeros(mask);
            int pm = mask ^ (1 << bit);
            sums[mask] = new Point(sums[pm].x + v[bit].x, sums[pm].y + v[bit].y);
        }

        HashSet<Long> evenKeys = new HashSet<>();
        HashSet<Long> oddKeys = new HashSet<>();
        List<Point> evenPoints = new ArrayList<>();

        for (int mask = 0; mask < full; ++mask) {
            long key = pairKey(sums[mask].x, sums[mask].y);
            if ((Integer.bitCount(mask) & 1) == 0) {
                if (!evenKeys.add(key))
                    return false;
                evenPoints.add(sums[mask]);
            } else {
                if (!oddKeys.add(key))
                    return false;
            }
        }

        for (Point c : evenPoints) {
            for (Point dxy : lattice) {
                int nx = c.x + dxy.x;
                int ny = c.y + dxy.y;
                if (oddKeys.contains(pairKey(nx, ny)))
                    continue;
                int count = 0;
                for (Point p : lattice) {
                    if (evenKeys.contains(pairKey(nx + p.x, ny + p.y))) {
                        count++;
                        if (count >= 2)
                            return false;
                    }
                }
            }
        }
        return true;
    }

    static boolean dfs(int nextIdx, int pos, int d, List<Point> reps, HashSet<Long> badDisp, Point[] selected,
            List<Point> lattice) {
        if (pos == d) {
            return testSelectedVectors(selected, lattice);
        }
        int remaining = d - pos;
        int limit = reps.size() - remaining;
        for (int i = nextIdx; i <= limit; ++i) {
            selected[pos] = reps.get(i);
            if (fourTupleHasForbiddenSum(selected, pos + 1, badDisp))
                continue;
            if (dfs(i + 1, pos + 1, d, reps, badDisp, selected, lattice))
                return true;
        }
        return false;
    }

    static boolean findForMAndDimension(int m, int d) {
        List<Point> lattice = circlePoints(m);
        if (lattice.isEmpty())
            return false;

        List<Point[]> pairs = oppositePairs(lattice);
        if (pairs.size() < d)
            return false;

        List<Point> reps = new ArrayList<>();
        for (Point[] pr : pairs) {
            Point a = pr[0];
            Point b = pr[1];
            boolean takeA = (a.x > b.x) || (a.x == b.x && a.y > b.y);
            reps.add(takeA ? a : b);
        }

        HashSet<Long> badDisp = buildBadDisplacements(lattice);
        int u = reps.size();
        int firstMax = u - d;
        if (firstMax < 0)
            return false;

        Point[] selected = new Point[d];

        for (int first = 0; first <= firstMax; ++first) {
            selected[0] = reps.get(first);
            if (dfs(first + 1, 1, d, reps, badDisp, selected, lattice))
                return true;
        }
        return false;
    }

    static long solveRSq(long n) {
        if (n <= 2)
            return 1;

        int d = 1;
        long capacity = 1;
        while (capacity < n) {
            d++;
            if (d >= 64) {
                capacity = Long.MAX_VALUE;
                break;
            }
            capacity <<= 1;
        }

        int m = 1;
        while (true) {
            if (oppositePairCountByFactorization(m) >= d) {
                if (findForMAndDimension(m, d)) {
                    return m;
                }
            }
            m++;
        }
    }

    public static String solve() {
        return Long.toString(solveRSq(500));
    }

    public static void main(String[] args) {
        if (solveRSq(2) != 1 || solveRSq(4) != 5) {
            System.err.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}