情景对话 牛妹：你爱我吗？小宝：当然啦，无论发生什么我都会爱你的， 牛妹：给出一个长度为n{n}n字符串S{S}S，有Q{Q}Q个查询，第i{i}i个查询给出两个整数li{l_i}liri{r_i}ri，询问有多少对不同的整数x,y{x,y}x,y满足li≤x≤y≤ri{l_ile xle yle r_i}li≤x≤y≤ri，并且Sx,Sx+1,...,Sy1,Sy{S_x,S_{x+1},...,S_{y-1},S_y}Sx,Sx+1,...,Sy1,Sy构成一个回文串， 小宝：...， 牛妹：你要是答不出来，就说明你不爱我！！！
情景对话 牛妹：你爱我吗？ 小宝：爱呀，当然爱呀！ 牛妹：那如果我让你查询回文串的话，你还会爱我吗? 小宝：当然啦，无论发生什么我都会爱你的。 牛妹：给出一个长度为n{n}n字符串S{S}S，有Q{Q}Q个查询，第i{i}i个查询给出两个整数li{l_i}li ri{r_i}ri，询问有多少对不同的整数x,y{x,y}x,y满足li≤x≤y≤ri{l_ile xle yle r_i}li≤x≤y≤ri，并且Sx,Sx+1,...,Sy−1,Sy{S_x,S_{x+1},...,S_{y-1},S_y}Sx,Sx+1,...,Sy−1,Sy构成一个回文串。 小宝：...（这么难的问题我不会呀┭┮﹏┭┮）。 牛妹：你要是答不出来，就说明你不爱我！！！哼。 小宝：...（大家快来救救孩子吧┭┮﹏┭┮）。 为了帮助小宝和牛妹巩固他们坚实的爱情，请你帮助小宝回答这个问题。 “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
（图片来源网络，侵删）
