P16183 [ICPC 2014 NAIPC] Two Knight' s Poem

Two chess knights have decided to collaborate on writing short, one-line poems. They have obtained the use of a laptop to type their poetry. The laptop keyboard is composed of 4 rows of 10 keys. 30 of these are symbol keys, 4 are Shift keys, and 6 are Space keys. :::align{center}  ::: Note that the **Shift** and **Space** keys, which are usually extra-wide keys on a keyboard, are treated here as multiple individual keys that each have the same effect. The knights will type the poem by making moves, one at a time, that are valid for a chess knight. A chess knight can move two positions vertically and then one horizontally, or one position vertically and then two horizontally. For example, from the **D** key, a knight can move to any of these keys: **Q**, **Z**, **T**, **B**, the second **Shift** key from the left, and the second **Space** key from the left. One knight always begins each poem on the left-most **Shift** key. The other knight always begins on the right-most **Shift** key. Either knight may move first, and either may make multiple consecutive moves. The knights cannot occupy the same key. Each move of a knight will type at most one character, adding to the poem. Landing on a symbol key or **Space** key will type one character. A knight landing on a symbol key types the upper value of that key when the other knight is on a **Shift** key; otherwise, the lower value is typed. Landing on a **Space** key always types a single space character, regardless of whether the other knight is on a **Shift** key. Landing on a **Shift** key does not add anything to the poem.

There will be several test cases in the input. Each test case will consist of a string on a single line, representing a poem. Each poem will consist of 1 to 100 characters inclusive, using only characters from the symbol keys on the keyboard and spaces. No poem will begin or end with a space. The input will end with a line with a single asterisk (`*`).

For each poem, output 1 if the knights can type the poem, or 0 if they cannot. Output each number on its own line, with no spaces. Do not print any blank lines between outputs.