Description

Since childhood, Suika has had a dream: to invite all the residents of the village to a banquet. Even after being defeated by Reimu (Língmèng) when she caused an incident last time, she did not give up and prepared a countless number of invitations well before the Lantern Festival.

Now, with the banquet about to begin, Suika still has a huge pile of invitations left to deliver. According to rigorous calculations by the great mathematician Cirno (Qílùnuò), by 2018 the population of Gensokyo has far exceeded that of the outside world, making the invitation task extremely difficult.

However, with her "ability to manipulate density," Suika can split into many Suikas of different sizes to deliver the invitations. Because the small Suikas move too slowly, she decides to let only the big Suikas go deliver the invitations.

Initially, there are $S$ Suikas. Then, every second, each big Suika splits into two Suikas: one big and one small. At the same time, the small Suikas produced in the previous second accumulate energy and grow into big Suikas.

Intuitively, here is what happens during the first four seconds when starting with only one big Suika (big Suika is denoted by "B", small Suika by "L"):

(It is easy to see that the initial big Suika splits into one big and one small after one second; in the next second, the newly produced big Suika splits again, while the small Suika from the previous second grows into a big Suika.)

However, our "Little Pandemonium" realized a serious problem: after an infinite amount of time, the number of Suikas becomes too large. So she decides that each time only the big Suikas within an interval will go deliver the invitations, and now she wants to know for each query how many invitations can be delivered.

If you can help her accomplish this task, she will give you two rewards — 100 points and an invitation to the banquet!

Input Format

The first line contains $S$ uppercase letters $\verb!B!$ or $\verb!L!$, representing the initial states of the Suikas.

Then an integer $n$, the number of queries.

Each of the next $n$ lines contains two integers $l, r$, representing the query interval.

Output Format

Output $n$ lines. Each line contains an integer $k$, the number of big Suikas in the interval $[l,r]$.

B
2
2 3
1 5

1
3

Hint

Constraints:

Translated by ChatGPT 5