기댓값

Eric은 임의의 정수를 만들어 내는 간단한 방식을 고안했다. 정수 $n$이 주어지면, 이 방식은 $0$부터 $n-1$까지의 정수 중 하나를 균등한 확률로 출력한다. 예를 들어 $n = 3$이면 $0$, $1$, $2$를 각각 $1/3$의 확률로 출력한다.

이제 Eric은 조금 더 복잡한 방식을 만들려고 한다. 서로 독립인 두 개의 생성기를 준비하고, 두 출력을 비트 단위 XOR 게이트에 넣는다. 이 게이트는 두 입력의 비트 단위 배타적 논리합(exclusive or)을 돌려준다. 친구 Nick은 그 결과의 기댓값이 궁금하다. 이 기댓값을 구하여라.

확률변수의 기댓값은 그 평균값이다. 음이 아닌 정수 값을 갖는 확률변수 $\xi$에 대해 기댓값은

$\mathbf{E}[\xi] = \sum_{i=0}^{\infty} i \cdot p_i$

로 계산할 수 있으며, 여기서 $p_i$는 $\xi$가 $i$와 같을 확률이다.

정확한 기댓값은 항상 유리수이므로, 반올림한 소수가 아니라 정확한 값으로 답해야 한다.

첫째 줄에 테스트 케이스의 수 $k$ ($1 \le k \le 1000$)가 주어진다. 이어지는 $k$개의 줄에는 각각 하나의 정수 $n$ ($1 \le n \le 10^9$)이 주어진다.

각 테스트 케이스마다, 두 생성기 출력의 XOR에 대한 정확한 기댓값을 기약분수 $p/q$ 형태로 출력한다. 여기서 $q \ge 1$이고 $\gcd(p, q) = 1$이다. 값이 정수인 경우에도 분모 $1$을 붙여서 (예: $0/1$) 출력한다. 각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.