题目描述

给定一个仅含小写字母的字符串 $s$，求它的最长回文子序列的长度。

子序列：从原串中删去若干字符（可以不删）、剩下字符保持原顺序得到的串。回文：正读反读相同。

输入格式

一行一个字符串 $s$。

输出格式

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

输入样例 1

bbbab

输出样例 1

4

说明

bbbb 是一个长度为 4 的回文子序列。

数据范围

$1 \le |s| \le 1000$。