class Solution {
    private static final int MOD = 1337;

    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        int upper = (int) Math.pow(10, n) - 1;
        int lower = upper / 10;
        for (int i = upper; lower < i; i--) {
            long p = toPalindrome(i, n);
            int sqrt = (int) Math.sqrt(p);
            for (int j = upper; sqrt <= j; j--) {
                if (p % j != 0L) continue;
                int ratio = (int) (p / j);
                if (lower < ratio && ratio <= upper)
                    return (int) (p % MOD);
            }
        }
        return -1;
    }

    private long toPalindrome(int num, int n) {
        int[] digits = new int[2 * n];
        for (int hi = n, lo = n - 1; 0 <= lo; hi++, lo--) {
            int digit = num % 10;
            digits[hi] = digit;
            digits[lo] = digit;
            num /= 10;
        }
        long p = 0L, base = 1L;
        for (int i = 0; i < 2 * n; i++) {
            p += digits[i] * base;
            base *= 10L;
        }
        return p;
    }
}