두 나이트의 시

체스 나이트 두 마리가 한 줄짜리 짧은 시를 함께 쓰기로 했다. 시를 찍을 노트북도 한 대 구했다. 이 노트북 자판은 10개짜리 키 줄 4개, 모두 40개 키로 이루어진다. 그중 30개는 문자 키, 4개는 Shift 키, 6개는 Space 키다.

보통 자판에서 Shift 키와 Space 키는 폭이 넓은 키 하나지만, 여기서는 같은 효과를 내는 여러 개의 독립된 키로 본다.

자판 배치는 다음과 같다.

1행:  q   w   e   r   t   y   u   i   o   p
2행:  a   s   d   f   g   h   j   k   l   ;
3행:  z   x   c   v   b   n   m   ,   .   /
4행:  Sh  Sh  Sp  Sp  Sp  Sp  Sp  Sp  Sh  Sh

Sh는 Shift 키, Sp는 Space 키다. 문자 키의 윗값은 알파벳 키의 경우 대문자이고, ;, ,, ., /의 윗값은 차례로 :, <, >, ?다.

두 나이트는 체스 나이트의 이동 규칙에 맞게 한 번에 한 마리씩 움직여 시를 찍는다. 나이트는 세로로 두 칸 간 다음 가로로 한 칸, 또는 세로로 한 칸 간 다음 가로로 두 칸 움직인다. 예를 들어 d 키에서는 q, z, t, b, 왼쪽에서 두 번째 Shift 키, 왼쪽에서 두 번째 Space 키로 갈 수 있다.

한 나이트는 항상 맨 왼쪽 Shift 키에서 시작하고, 다른 나이트는 항상 맨 오른쪽 Shift 키에서 시작한다. 어느 쪽이 먼저 움직여도 되고, 한쪽이 연달아 여러 번 움직여도 된다. 두 나이트가 같은 키를 함께 차지할 수는 없다.

나이트가 한 번 움직일 때 시에 붙는 문자는 많아야 하나다. 문자 키나 Space 키에 내려앉으면 문자 하나가 찍힌다. 문자 키에 내려앉은 나이트는 다른 나이트가 Shift 키 위에 있으면 그 키의 윗값을, 아니면 아랫값을 찍는다. Space 키에 내려앉으면 다른 나이트가 Shift 키 위에 있든 없든 공백 문자 하나가 찍힌다. Shift 키에 내려앉으면 시에는 아무것도 붙지 않는다.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스는 시 하나를 담은 한 줄이다. 시의 길이는 1자 이상 100자 이하이고, 자판의 문자 키로 찍히는 문자와 공백만 쓴다. 공백으로 시작하거나 공백으로 끝나는 시는 없다. 입력의 마지막 줄에는 별표 하나(*)만 있다.

시마다 두 나이트가 그 시를 찍을 수 있으면 1을, 찍을 수 없으면 0을 출력한다. 한 줄에 숫자 하나씩 출력하고, 공백이나 빈 줄은 넣지 않는다.