Aristides 有一个随机数生成器。每次他向随机数生成器请求时，它都会均匀地返回一个 $1$ 到 $N$ 之间的随机整数。

Aristides 的朋友 Iorgos 会逐一记录返回的数字。Aristides 会不断请求随机数，直到 Iorgos 叫停。为了分析随机数生成器的随机性，Iorgos 会在 $1$ 到 $N$ 之间的每个数字都至少被返回两次后，立即叫停 Aristides。

Aristides 已经向随机数生成器请求了 $K$ 次。随机数生成器返回的第 $i$ 个数字是 $A_i$。由于 Iorgos 还没有叫停，他知道 $1$ 到 $N$ 之间的整数中，至少有一个数字还没有被返回至少两次。

Aristides 想知道直到 Iorgos 叫停他为止，还需要请求的期望次数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100,000$)，表示测试用例的数量。每个测试用例的第一行包含两个整数 $N$ ($1 \le N \le 3,000$) 和 $K$ ($0 \le K \le 100,000$)，分别表示返回整数的范围和已经请求的次数。每个测试用例的第二行包含 $K$ 个整数 $A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$)，表示前 $K$ 次返回的数字。保证 $1$ 到 $N$ 之间的整数中，至少有一个数字还没有被返回至少两次。同时保证所有测试用例中 $K$ 的总和不超过 $100,000$。

输出格式

对于每个测试用例，输出一行，表示 Aristides 直到被 Iorgos 叫停还需要请求的期望次数。如果你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$，则视为正确。

样例

输入 1

4 
1 0 
1 1 
1 
2 10 
2 2 2 2 2 2 2 2 2 2 
3 0

输出 1

2.000000000 
1.000000000 
4.000000000 
9.638888889

说明

样例 1 的解释

对于第一个样例，随机数生成器返回的前两个数字总是 $1$。因此，通过请求随机数生成器两次，从 $1$ 到 $N$ 的每个数字都至少被返回了两次。

样例 2 的解释

对于第二个样例，Aristides 已经请求了一次随机数。因此，他只需要再请求一次。