# coreBugZJ

## PALIN - SPOJ 5. The Next Palindrome

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

### Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

### Output

For each K, output the smallest palindrome larger than K.

### Example

Input:
2
808
2133

Output:
818
2222

Warning: large Input/Output data, be careful with certain languages

1 (defun digit-succ(x)
2 (elt "0123456789A" (position x "*0123456789")))
3 4 (let ((num (read)))
5 (dotimes (ca num)
6 (let* ((str (read-line))
7 (len (length str))
8 (cmp 0)
9 (i nil)
10 (j nil))
11 (dotimes (i (floor (/ (1+ len) 2)))
12 (setf j (1- (- len i)))
13 (when (char> (elt str i) (elt str j))
14 (setf cmp 1))
15 (when (char< (elt str i) (elt str j))
16 (setf cmp -1))
17 (setf (elt str j) (elt str i)))
18 (when (<= cmp 0)
19 (setf i (1- (floor (/ (1+ len) 2))))
20 (setf j (if (oddp len) i (1+ i)))
21 (do ()
22 ((or (minusp i) (char< (elt str i) #\9)))
23 (setf (elt str i) #\0)
24 (setf (elt str j) #\0)
25 (decf i)
26 (incf j))
27 (when (minusp i)
28 (setf (elt str 0) #\1)
29 (write-string str)
30 (write-char #\1))
31 (when (not (minusp i))
32 (setf (elt str i) (digit-succ (elt str i)))
33 (setf (elt str j) (elt str i))
34 (write-string str)))
35 (when (plusp cmp)
36 (write-string str))
37 (fresh-line))))
38 39 posted on 2012-02-19 16:18 coreBugZJ 阅读(296) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithmLisp 