古老王国的幸运数

题目描述

在遥远的古代，有一个被遗忘的神秘王国。王国的守护者们掌握着一种古老的符文力量，这些符文由大小写字母组成，并被精心雕刻在王国的圣物之上。据说，这些符文隐藏着王国的幸运数，而找到这个幸运数就能解开王国深处的秘密。然而，幸运数并非直接可见，而是需要通过一系列的转换和计算才能得到。

你是一位勇敢而智慧的探险家，偶然间在一次探险中发现了这个王国的遗迹，并幸运地获得了刻有符文的圣物。为了揭开这个王国的秘密并找到幸运数，你需要根据特定的规则转换这些符文，并在转换后的符文中找到最长的回文子序列，这个回文子序列的长度就是王国的幸运数。

你获得了一个刻有符文的圣物，上面刻有一个由大小写字母组成的字符串 s。你的任务是：

根据以下规则转换字符串中的每个字符：

1. 字符是大写字母，则将其转换为对应的小写字母。
2. 再将小写字母，在字母表中向后移动 3 位。如果移动后超出了字母表的范围，则从头开始计算（例如：z 移动 3 位后变为 c）。
3. 在转换后的符文中，找到最长的回文子序列。最长回文子序列的长度，这就是王国的幸运数。

输入格式

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

输出格式

输出一个整数，表示转换后字符串中最长回文子序列的长度，即王国的幸运数。

样例

样例输入 1

Qzqj

样例输出 1

3

数据范围

• 字符串 s 的长度：1 ≤ |s| ≤ 1000
• 字符串仅包含大小写英文字母

知识点与难度

• 知识点：动态规划提高、第十二讲(Level4)
• 难度：Mid

测试点分布