问题描述

老师决定给他的大别野安装一道新的围栏。这道围栏由 $n$ 块大小相同的木板排成一列组成。老师望着这些木板，突然灵光一闪——他要用自己收藏的 $m$ 种不同颜色的油漆来粉刷这道围栏。

老师是一个有原则的人。他希望围栏的粉刷方案既美观又独特，因此制定了以下规则：

1. 单色原则：每块木板必须被涂成一种颜色。
2. 双色限制：整个围栏只能使用恰好两种不同的颜色。
3. 连续涂色：相同颜色的木板必须形成一个连续的序列。换句话说，对于任意两块颜色相同的木板，它们之间的所有木板也必须涂成相同的颜色。

老师的油漆库存有限——第 $i$ 种颜色的油漆最多只能涂 $a_i$ 块木板。他不想再购买额外的油漆，因此需要在现有条件下计算出所有可能的粉刷方案。

你的任务是帮助老师计算出满足上述所有条件的粉刷方案的总数。

两种方案被视为不同：当且仅当存在至少一块木板在两种方案中被涂成了不同的颜色。

输入格式

第一行输入一个整数 $t$（ $1 \leq t \leq 10^4$ ），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（ $2 \leq n, m \leq 2 \cdot 10^5$ ），分别表示围栏的木板数量和油漆颜色种类数。

每个测试用例的第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$（ $1 \leq a_i \leq n$ ），其中 $a_i$ 表示第 $i$ 种颜色的油漆最多能涂的木板数量。

输出格式

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

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

样例输入

3
5 2
2 4
5 2
3 4
12 3
5 9 8

样例输出

4
6
22

说明

第一个测试用例：
共有 4 种粉刷方案（以下为木板从左到右的颜色序列）：

1. [1, 2, 2, 2, 2]
2. [1, 1, 2, 2, 2]
3. [2, 2, 2, 1, 1]
4. [2, 2, 2, 2, 1]