Smallest Palindrome with Prime Digit Sum

Given an integer \(M\), find the smallest palindrome number \(P\) such that \(P \ge M\) and the sum of the digits of \(P\) is a prime number.

A number is a palindrome if it reads the same forwards and backwards (for example, 121 and 1331). The digit sum of a number is the sum of all its digits. A number is prime if it is greater than 1 and has no divisors other than 1 and itself.

For instance, if \(M = 123\), the smallest palindrome \(\ge 123\) is 131, and the sum of the digits of 131 is \(1+3+1 = 5\), which is prime. Hence, the output is 131.

inputFormat

The input consists of a single line containing an integer \(M\) (\(1 \le M \le 10^9\) or as per problem constraints) from stdin.

outputFormat

Output a single integer to stdout which is the smallest palindrome \(P\) such that \(P \ge M\) and the sum of its digits is a prime number.

123

131