F. Distinct
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a program that consists of $$$n$$$ instructions. Initially, a single variable $$$x$$$ is assigned to $$$1$$$.

Afterwards, the instructions are of two types:

  • divide $$$x$$$ by $$$2$$$ ($$$x = \lfloor{x/2}\rfloor$$$, integer division).
  • multiply $$$x$$$ by $$$2$$$.

You are given $$$m$$$ queries of the following format:

  • query $$$l$$$ $$$r$$$ $$$-$$$ how many distinct values is $$$x$$$ assigned to if all the instructions between the $$$l_{th}$$$ one and the $$$r_{th}$$$ one inclusive are executed without changing the order ?
Input

The first line contains a single integer $$$t$$$ $$$(1\leq t \leq 1000)- $$$the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n,q \leq 10^{6})- $$$the number of instructions in the program and the number of queries.

The second line of each testcase contains a program $$$-$$$ a string of $$$n$$$ characters: each character is either '$$$*$$$' or '$$$/$$$' $$$-$$$ multiply and divide instruction, respectively.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1\leq l \leq r \leq n)-$$$ the description of the query.

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^{6}$$$. The sum of $$$q$$$ over all test cases doesn't exceed $$$10^{6}$$$.

Output

For each test case, print $$$q$$$ integers $$$-$$$ for each query $$$l$$$,$$$r$$$, print the number of distinct values variable $$$x$$$ is assigned to if all the instructions between the $$$l_{th}$$$ one and the $$$r_{th}$$$ one inclusive are executed without changing the order and $$$x$$$ always starts with $$$1$$$.

Example
Input
2
12 5
*/**///*/*//
1 4
2 7
6 10
1 12
4 8
5 3
*//**
1 3
2 5
2 4
Output
3
2
2
4
3
3
2
2