该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个由 $n$ 条指令组成的程序。最初，一个变量 $x$ 被赋值给 $0$ 。之后，指令有两种类型：

• 将 $x$ 增加 $1$ ；
• 将 $x$ 减少 $1$ 。

您将得到 $m$ 个查询，其格式如下：

• 查询 $l$ $r$ - 如果忽略第 $l$ 个指令和第 $r$ 个指令（包括第 $l$ 个指令和第 $r$ 个指令）之间的所有指令，并且在不改变顺序的情况下执行其他指令，那么 $x$ 被分配给多少个不同的值？

输入格式

输入

第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) - 测试用例数。

然后是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ( $1 \le n, m \le 2 \cdot 10^5$ )--程序指令数和查询次数。

每个测试用例的第二行包含一个程序--一个由 $n$ 个字符组成的字符串：每个字符要么是 "+"，要么是"-"--分别是递增指令和递减指令。

接下来的每 $m$ 行包含两个整数 $l$ 和 $r$ （ $1 \le l \le r \le n$ ）--查询描述。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式

输出

为每个测试用例打印 $m$ 个整数 - 为每个查询 $l$ , $r$ 打印变量 $x$ 被赋值的不同值的个数，前提是忽略 $l$ （第 1 个）和 $r$ （第 3 个）之间的所有指令，并在不改变顺序的情况下执行其余指令。

2
8 4
-+--+--+
1 8
2 8
2 5
1 1
4 10
+-++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4

1
2
4
4
3
3
4
2
3
2
1
2
2
2

注

第一个测试用例中的每个查询所保留的指令是

1. 空程序 - $x$ 只等于 $0$ ；
2. "-" - $x$ 的值为 $0$ 和 $-1$ ；
3. "---+" - $x$ 的值为 $0$ 、 $-1$ 、 $-2$ 、 $-3$ 、 $-2$ --其中有 $4$ 个不同的值；
4. "+--+--+"--不同的值有 $1$ ， $0$ ， $-1$ ， $-2$ 。