func largestPalindrome(n int) int {
	// mod 1337
	if n == 1 {
		return 9
	}
	upper := int(math.Pow10(n)) - 1
	lower := upper / 10
	for i := upper; lower < i; i-- {
		pa := toPalindrome(i)
		bound := int(math.Sqrt(float64(pa)))
		for j := upper; j >= bound; j-- {
			if pa%j != 0 {
				continue
			}
			if ratio := pa / j; lower < ratio && ratio <= upper {
				return pa % 1337
			}
		}
	}
	return -1 // Not found
}

func toPalindrome(x int) (res int) {
	num := make([]int, 64)
	lo, hi := 0, 0
	for ; x != 0; x /= 10 {
		num[lo] = x % 10
		lo++
	}
	copy(num[lo:], num[:lo])
	for hi, lo = lo, lo-1; 0 <= lo; lo, hi = lo-1, hi+1 {
		num[lo] = num[hi]
	}
	for i, base := 0, 1; i < hi; i, base = i+1, base*10 {
		res += num[i] * base
	}
	return
}