雅典娜刚刚完成了他最新的音乐作品的创作,并将于明天向雅典人民展示。不幸的是,旋律相当沉闷,很可能不会受到热烈的欢迎。
他的歌曲由 $$$n$$$ 音符组成,我们将其视为正整数。一首歌的多样性是指它包含的不同音符的数量。作为音乐的赞助人,尤特普守护着作曲家并在创作新旋律的整个过程中指导他们。她决定帮助雅典娜改变他的歌曲,使其更加多样化。
作为一个小女神,她不能随意改变歌曲。相反,对于歌曲中的每个 $$$n$$$ 音符,她可以保持原样,也可以将其增加 $$$1$$$。
将歌曲作为描述音符的整数序列,找出可实现的最大多样性。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例,每个测试用例用两行描述。
在每个测试用例的第一行有一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) 表示歌曲的长度。下一行包含一系列 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ $$$(1 \leq x_1 \leq x_2 \leq \ldots \leq x_n \leq 2 \cdot n)$$$,描述歌曲。
所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,您应该输出一行恰好包含一个整数,即歌曲的最大多样性,即最终序列中不同元素的最大可能数量。
示例
输入 #1
5 6 1 2 2 2 5 6 2 4 4 6 1 1 3 4 4 5 1 1 6 1 1 1 2 2 2
输出 #1
5 2 6 1 3
注意
在第一个测试用例中,Euterpe 可以增加第二个、第五个和第六个元素,得到序列 $$$1, \underline{3}, 2, 2, \underline{6}, \underline{7}$$$,其中有 $$$5$$$ 不同的元素(增加的元素带有下划线)。
在第二个测试用例中,Euterpe可以增加第一个元素以获得序列$$$\underline{5}, 4$$$,其中有$$$2$$$不同的元素。
在第三个测试用例中,Euterpe可以将第二个、第五个和第六个元素相加,得到序列$$$1, \underline{2}, 3, 4, \underline{5}, \underline{6}$$$,其中有$$$6$$$个不同的元素。