Problem K
Two Knights' 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.

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  Q  |  W  |  E  |  R  |  T  |  Y  |  U  |  I  |  O  |  P  |
|     |     |     |     |     |     |     |     |     |     |
|  q  |  w  |  e  |  r  |  t  |  y  |  u  |  i  |  o  |  p  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  A  |  S  |  D  |  F  |  G  |  H  |  J  |  K  |  L  |  :  |
|     |     |     |     |     |     |     |     |     |     |
|  a  |  s  |  d  |  f  |  g  |  h  |  j  |  k  |  l  |  ;  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  Z  |  X  |  C  |  V  |  B  |  N  |  M  |  <  |  >  |  ?  |
|     |     |     |     |     |     |     |     |     |     |
|  z  |  x  |  c  |  v  |  b  |  n  |  m  |  ,  |  .  |  /  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|     |     |     |     |     |     |     |     |     |     |
|Shift|Shift|Space|Space|Space|Space|Space|Space|Shift|Shift|
|     |     |     |     |     |     |     |     |     |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

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.

Input

There will be up to 10 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 (’*’).

Output

For each poem, output 1 if the knights can type the poem, or 0 if they cannot.

S,veA,eVE,aU
S,veA,eVE,aUc
CAlmimg eventa
CAL
*

1
0
1
1