Longest Palindromic Subsequence

**Problem.** A string s per line (read until EOF). Print, per line, the length of its longest palindromic subsequence. **Constraints:** up to 50 lines; 1 ≤ |s| ≤ 2000; lowercase letters. O(n^2) interval DP; the two-pointer greedy is the planted trap.