Background

Special for beginners, ^_^

Description

阿强来到大街上，街上有 N 个人，编号为 1 ∼N 。简单起见，我们把每个人都看成一条线上的一个点。对每个合法的 i，第 i 个人的位置是 $x_i$。

这些人当中恰好有一个感染了 COVID-19，但我们不知道是哪一个。当一个被感染的人和一个未被感染的人之间的距离不超过 2 时，病毒会从前者传播到后者。如果我们等待足够长的时间，会有一些人（这些人由第一个感染者确定）被感染；这些人的数量被称作最终被感染的人数。

阿强希望求出最终被感染的人数的最小和最大可能的值，也就是最好和最坏情况下这个数的值。

Format

Input

第一行包含一个整数T$(1≤T≤2,000)$，表示数据组数。接下来是T组数据。
•每组数据的第一行包含一个整数N$(2≤N≤8)$。
•第二行包含N个整数$x_1,x_2, \dots, x_n (0≤x_i≤10)$，用空格隔开。

Output

对于每组数据，输出一行包含两个整数，用空格隔开，表示最终被感染的人数的最小值和最大值。

Samples

3
2
3 6
3
1 3 5
5
1 2 5 6 7

1 1
3 3
2 3

Limitation

1s, 1024KiB for each test case.