증가 수열 카드 게임

당신은 혼자서 카드 게임을 한다.

카드는 $\mathbf{N}$장 있다. $i$번째 카드에는 정수 $i$가 적혀 있다.

먼저 $\mathbf{N}$장의 카드를 무작위로 섞어 한 더미로 놓는다. 더미 맨 위의 카드를 손으로 가져온다. 그런 다음 더미가 빌 때까지 다음 과정을 반복한다.

• 더미 맨 위의 카드를 확인한다.

• 그 카드에 적힌 수가 마지막으로 가져온 카드에 적힌 수보다 크면 그 카드를 가져온다.

• 그렇지 않으면 그 카드를 버린다.

게임의 점수는 게임이 끝났을 때 손에 있는 카드의 수이다. 주어진 카드 수 $\mathbf{N}$에 대해 게임 점수의 기댓값은 얼마인가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1

$1 \le \mathbf{N} \le 10$.

테스트 세트 2

$1 \le \mathbf{N} \le 10^6$.

테스트 세트 3

$1 \le \mathbf{N} \le 10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄에는 더미에 있는 카드의 수를 나타내는 하나의 정수 $\mathbf{N}$가 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 (1부터 시작), y는 게임이 끝났을 때 점수의 기댓값이다.

y가 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ를 참고하라.