Reverse Numbers

Time limit1sMemory limit32 MB

Summary
Given up to 10000-digit numbers M, decide whether some N satisfies M = N + Rev(N).
Level

Medium7 of 10

Topics
String, Math, Implementation
Solved
No attempts yet

Problem

Numbers have many interesting properties. In this problem we look at one of them.

First, let us define the reverse of a number. For a number NN written in decimal as an…a1a0a_n \dots a_1 a_0, its reverse is the number a0a1…ana_0 a_1 \dots a_n obtained by writing the digits in the opposite order; we denote it Rev(N)\mathrm{Rev}(N). Any leading zeros produced this way are dropped. For example, Rev(123)=321\mathrm{Rev}(123) = 321 and Rev(7400)=47\mathrm{Rev}(7400) = 47.

You are given several natural numbers. For each number MM, decide whether there exists a natural number NN such that M=N+Rev(N)M = N + \mathrm{Rev}(N).

Input

The input consists of at most 10001 lines. Each line contains one positive integer with fewer than 10000 digits. The last line contains the number 00, which must not be processed.

Output

For each number MM in the input, print YES on its own line if there exists a natural number NN with M=N+Rev(N)M = N + \mathrm{Rev}(N), and NO otherwise.

Examples4

  1. Example 1

    Input
    1
2
11
13
14003
767513456469789456166547987979741366664879441
0
    Expected output
    NO
YES
YES
NO
YES
NO

  2. Example 2

    Input
    1
2
3
4
5
6
7
8
9
10
0
    Expected output
    NO
YES
NO
YES
NO
YES
NO
YES
NO
YES

  3. Example 3

    Input
    22
121
100
198
1000
0
    Expected output
    YES
YES
NO
YES
NO

  4. Example 4

    Input
    11
110
1010
1001
1000
1002
0
    Expected output
    YES
YES
YES
YES
NO
NO