난수 생성기

1부터 $N$까지의 정수를 균등한 확률로 반환하는 난수 생성기가 있다. 생성기가 수를 반환할 때마다 친구가 그 수를 하나씩 기록한다. $1$부터 $N$까지의 모든 수가 적어도 두 번씩 기록되는 즉시 친구가 생성기를 멈춘다.

생성기는 이미 $K$개의 수를 반환했고, $i$번째로 반환된 수는 $A_i$이다. 친구가 아직 멈추지 않았으므로 $1$부터 $N$까지의 수 중 적어도 하나는 아직 두 번 반환되지 않았다.

친구가 멈출 때까지 추가로 요청해야 하는 횟수의 기댓값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100{,}000$).

각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $K$가 주어진다 ($1 \le N \le 3{,}000$, $0 \le K \le 100{,}000$). $N$은 반환될 수의 범위이고 $K$는 이미 요청한 수의 개수이다.

각 테스트 케이스의 둘째 줄에는 $K$개의 정수 $A_1, A_2, \dots, A_K$가 주어진다 ($1 \le A_i \le N$). $K = 0$인 경우 이 줄은 비어 있다.

아직 모든 수가 두 번씩 반환되지는 않았다고 가정한다. 모든 테스트 케이스에 대한 $K$의 합은 $100{,}000$을 넘지 않는다.

각 테스트 케이스마다 친구가 멈출 때까지 추가로 요청해야 하는 횟수의 기댓값을 한 줄에 출력한다.

절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.

앞으로 필요한 기댓값은 지금까지 각 수가 몇 번 등장했는지가 아니라, 아직 한 번도 등장하지 않은 수의 개수와 정확히 한 번 등장한 수의 개수에만 의존한다.

$N = 1$이고 아직 아무 수도 보지 못한 경우 항상 $2$를 추가로 요청해야 한다. $N = 1$이고 $1$이 이미 한 번 등장한 경우 답은 $1$이다.