Items Between Bars in Query Ranges

You are given a string s consisting only of the characters * and |, where each * is an item and each | is a bar. You are also given a 2D integer array queries where queries[i] = [l, r] names the substring s[l..r], inclusive.

An item is between bars in a substring if there is at least one bar to its left and at least one bar to its right, both still inside that substring.

Return an integer array answer where answer[i] is the number of items between bars in the substring s[queries[i][0]..queries[i][1]].

Examples

Example 1

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation: In s[2..5] = "|**|", the two items between the two bars are between bars, so the answer is 2. In s[5..9] = "|***|", the three items are between bars, so the answer is 3.

Example 2

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation: In s[1..17] = "**|**|*****|**||*", the bars are at positions 3, 6, 12, 15, 16 and there are 9 items between the first and last of those bars. Each other query's range contains at most one bar, so no item in it has bars on both sides.