The Code A Doctor Loved

ID: 8416

Type: Default

1000ms

134MiB

Dr .: Peter, I've finally done it. Peter: What's wrong, Dr. David? Is it a silly invention again? Dr .: This table, this table.

Character	Sign
(Blank)	101
'	000000
,	000011
-	10010001
.	010001
?	000001
A	100101
B	10011010
Character	Sign
---
C	0101
D	0001
E	110
F	01001
G	10011011
H	010000
I	0111
J	10011000
Character	Sign
---
K	0110
L	00100
M	10011001
N	10011110
O	00101
P	111
Q	10011111
R	1000
Character	Sign
---
S	00110
T	00111
U	10011100
V	10011101
W	000010
X	10010010
Y	10010011
Z	10010000

Peter: What? This table is. Dr .: Okay, just do what you say. First, write your name on a piece of paper. Peter: Yes, "PETER POTTER". Dr .: Then, replace each character with the "code" in this table. Peter: Well, change "P" to "111" and "E" to "110" ... It's quite annoying.

111 110 00111 110 1000 101 111 00101 00111 00111 110 1000

became. It looks like a barcode. Dr .: All right. Then connect all the replaced strings and separate them by 5 characters. Peter: Yes, if you connect and separate.

11111 00011 11101 00010 11110 01010 01110 01111 10100 0

It turned out to be something like this. But what about the last "0" guy? Dr .: Add 0 to make it 5 letters. Peter: Well, there is only one 0 at the end, so I should add four more 0s. I was able to do it.

11111 00011 11101 00010 11110 01010 01110 01111 10100 00000

Dr .: Next, use this table.

Sign	Character
00000	A
00001	B
00010	C
00011	D
00100	E
00101	F
00110	G
00111	H
Sign	Character
---
01000	I
01001	J
01010	K
01011	L
01100	M
01101	N
01110	O
01111	P
Sign	Character
---
10000	Q
10001	R
10010	S
10011	T
10100	U
10101	V
10110	W
10111	X
Sign	Character
---
11000	Y
11001	Z
11010	(blank)
11011	..
11100	,
11101	-
11110	'
11111	?

Peter: How do you use this ... yeah! Now you're going to replace the code with a letter! Dr .: That's right. If it is "11111", go to "?", If it is "00011", go to "D". Peter: This is simple ... well, it became "? D-C'KOPUA". But it doesn't make sense. Dr .: Count the number of characters. Peter: It's 10 characters. Oh, "PETER POTTER" was 12 characters, but 2 characters are reduced. Dr .: Yes, you can use this table to reduce the number of letters. Now do the same thing in this sentence.

PETER PIPER PICKED A PECK OF PICKLED PEPPERS. A PECK OF PICKLED PEPPERS PETER PIPER PICKED. IF PETER PIPER PICKED A PECK OF PICKLED PEPPERS, WHERE'S THE PECK OF PICKLED PEPPERS PETER PIPER PICKED?

Peter: Gyogyo, the lines are separated, what do you do? Dr .: Due to space limitations, there are only 3 lines, but think of it as a long line with a space instead of a newline character. Peter: Yes, yes. There is a blank space between the lines. But it's a hassle ... Dr .: Then why not let the program do it?

So, instead of Peter, create a program that converts the read character string into a code and outputs it.

input

Given multiple datasets. Each dataset is given a line of strings (consisting of the characters contained in the table). The string contains at least 1 and no more than 100 characters.

The number of datasets does not exceed 200.

output

For each data set, output the converted character string on one line.

Example

Input

PETER POTTER

Output

?D-C'KOPUA

inputFormat

outputFormat

outputs it.