题目内容

小红书后端基础设施包含 $n$ 个服务器节点，编号 $1$ 到 $n$ 。

第 $i$ 个节点与相邻节点(即编号 $i-1$ 和 $i+1$ 的节点，如果存在)通过链路相连。

每一个节点都有它的传输信号限制，第 $i$ 个节点发送的数据至多只能经过 $d_i$ 条链路。

现需在若干节点部署服务点，确保每个节点均可在不超过其链路限制的范围内访问到至少一个服务点。

求最少需要部署的服务点数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $n(1≤n≤2×10^5)$ ，表示节点数。

第二行输入 $n$ 个整数 $d_1,d_2,…,d_n(0≤d_i≤n-1)$ ，表示第 $i$ 个节点的传输信号限制。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数，表示最少需要部署的服务点数。

样例1

输入

3
7
4 0 0 1 3 1 3
5
0 1 1 1 0
4
0 0 0 0

输出

3
3
4

说明

对于第一组测试教据,节点覆盖区间分别为 $[1，5]，[2，2]，[3，3]，[3,5]，[2,7]，[5,7]，[4，7]$ ，可选服务点位置为 $2,3,5$ ，共 $3$ 个。

对于第三组测试数据，$D=[0,0,0,0]$ 时，所有区间为自身，需在每个节点设服务点，共 $4$ 个。