기어 조합하기

사회가 빠르게 발전하면서 고정밀 시계의 수요가 계속 늘고 있다. 최근 China Clock Production Company는 다양한 시각을 표현할 수 있는 새로운 종류의 시계를 개발하고 있다.

이 새로운 시계는 특이한 방식으로 현재 시각을 표시한다. 시계는 여러 개의 바늘로 이루어져 있고, 각 바늘은 기어 하나로 제어된다. 모든 기어는 한 주기마다 톱니 하나씩 동기화되어 회전한다. 다만 기어마다 톱니의 개수는 다를 수 있다. 톱니가 $t$개인 기어가 있으면 그에 대응하는 바늘은 $t$가지 서로 다른 방향을 가리킬 수 있고, 각 방향을 $0, 1, 2, \cdots, t-1$이라 하며 $0$이 초기 방향이다. 또한 시계에 바늘이 $n$개 있고 $i$번째 바늘이 톱니 $t\_i$개인 기어로 제어된다면, $k$ 주기의 시간이 지난 뒤 $i$번째 바늘은 $k \bmod t\_i$를 가리킨다.

톱니가 $t$개인 기어의 가격은 $t$위안이다. 총 예산 $b$위안이 주어질 때, 바늘 방향의 유효한 조합 수가 최대가 되도록 기어 조합을 설계해야 하며, 기어에 드는 총비용은 예산을 넘지 않아야 한다. 방향 조합 $(d\_1, d\_2, \cdots, d\_n)$이 유효하다는 것은 어떤 음이 아닌 정수 $k$에 대해 $(k \bmod t\_1, k \bmod t\_2, \cdots, k \bmod t\_n)$ 로 쓸 수 있다는 뜻이고, 여기서 $t\_i$는 $i$번째 기어의 톱니 개수다. 답이 너무 클 수 있으므로 자연로그($e = 2.718281828\cdots$를 밑으로 하는 로그) 값을 출력한다.

첫째 줄에 테스트 케이스의 수를 나타내는 정수 $T$ $(1 \leq T \leq 30\;000)$가 주어진다. 각 테스트 케이스는 총 예산을 나타내는 정수 $b$ $(1 \leq b \leq 30\;000)$ 하나로 이루어진 한 줄이다.

각 테스트 케이스마다 유효한 조합 수의 최댓값의 자연로그를 절대 또는 상대 오차 $10^{-6}$ 이하로 한 줄에 출력한다.

두 번째 예제 데이터에서는 톱니가 3개인 기어와 톱니가 4개인 기어를 쓰면 방향 조합 12가지를 얻을 수 있고, 총비용은 정확히 7이다. 따라서 $\ln 12$의 값인 약 2.484906650을 출력해야 한다.