You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

在遥远的古代，有一个被遗忘的神秘王国。王国的守护者们掌握着一种古老的符文力量，这些符文由大小写字母组成，并被精心雕刻在王国的圣物之上。据说，这些符文隐藏着王国的幸运数而找到这个幸运数就能解开王国深处的秘密。然而，幸运数并非直接可见，而是需要通过一系列的转换和计算才能得到。你是一位勇敢而智慧的探险家，偶然间在一次探险中发现了这个王国的遗迹，并幸运地获得了刻有符文的圣物。为了揭开这个王国的秘密并找到幸运数，你需要根据特定的规则转换这些符文，并在转换后的符文中找到最长的回文子序列，这个回文子序列的长度就是王国的幸运数。

你获得了一个刻有符文的圣物，上面刻有一个由大小写字母组成的字符串S。 你的任务是： 根据以下规则转换字符串中的每个字符： 1.大写字母，则将其转换为对应的小写字母。 2.再将小写字母，在字母表中向后移动3位。如果移动后超出了字母表的范围，则从头开始计算（例如：z移动3位后变为c）。 3.在转换后的符文中，找到最长的回文子序列。最长回文子序列的长度，这就是王国的幸运数。

输入

【输入格式】 输入一行字符串s，表示圣物上的符文。字符串的长度在1到1000之间，且仅包含大小写字母

输出

一个整数，表示最长回文子序列的长度

Samples

Qzqj

3

Limitation

1s, 1024KiB for each test case.