Longest Palindromic Subsequence Queries

Given a string \( S \) and several queries, each query asking for the longest palindromic subsequence in a substring \( S[L:R] \) (1-indexed), your task is to determine the length of the longest palindromic subsequence for each query.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Note: The string \( S \) will contain only lowercase alphabet characters.

inputFormat

The input consists of multiple lines. The first line contains the string ( S ). The second line contains an integer ( Q ), representing the number of queries. Each of the following ( Q ) lines contains two integers ( L ) and ( R ), which are the 1-indexed starting and ending positions of the substring.

outputFormat

For each query, output a single integer representing the length of the longest palindromic subsequence in the substring ( S[L:R] ). Each answer should be printed on a new line.## sample

banana
3
1 3
1 6
3 6

1
5
3