Random Number Generator

There is a random number generator that returns an integer from $1$ to $N$ uniformly at random. Each time the generator returns a number, a friend writes it down. The friend stops the generator as soon as every integer from $1$ to $N$ has been recorded at least twice.

The generator has already returned $K$ numbers, and the $i$-th returned number is $A_i$. Since the friend has not stopped the generator yet, at least one integer from $1$ to $N$ has been returned fewer than twice.

Compute the expected number of additional requests needed until the friend stops the generator.

The first line contains the number of test cases $T$ ($1 \le T \le 100{,}000$).

The first line of each test case contains two integers $N$ and $K$ ($1 \le N \le 3{,}000$, $0 \le K \le 100{,}000$). $N$ is the range of returned integers and $K$ is the number of integers already requested.

The second line of each test case contains $K$ integers $A_1, A_2, \dots, A_K$ ($1 \le A_i \le N$). This line is empty when $K = 0$.

It is guaranteed that not every integer has been returned twice yet. The sum of $K$ over all test cases does not exceed $100{,}000$.

For each test case, print the expected number of additional requests until the friend stops the generator, one per line.

An answer is accepted if its absolute or relative error is at most $10^{-6}$.

The expected remaining count depends only on how many integers have never appeared and how many have appeared exactly once, not on the full history.

When $N = 1$ and nothing has been seen yet, $2$ more requests are always needed. When $N = 1$ and $1$ has already appeared once, the answer is $1$.