Description

大写字母与数字的映射关系如下表所示： ADGJMPSVY 1 2 3 BEHKNQTWZ 4 5 6 CFILORUX 7 8 9 说明字母A可以表示数字1，也可以表示数字2和3。其他同理。 给出一个由2个大写字母表示的字符串，请找出其能够表示的最小素数。如果不存在，请输出-1。

Input

输入数据有N组。每组测试数据由一个包含2个大写字母的字符串组成。

Output

输出数据有N行，每行表示一组测试数据的输出结果。

Sample

Input

1
OJ

Output

71