수열과 병규

특이한 수열을 만드는 게 취미인 병규는 다음과 같은 수열 $a$를 만들었다.

$a\_1 = 1, a\_2 = 2$이며 모든 양의 정수 $n$에 대해 아래 식을 만족한다.

• $a\_{3n} = 2a\_n + 2a\_{n+1} + 1$
• $a\_{3n+1} = 2a\_{n+2} - 1$
• $a\_{3n+2} = -2a\_{n+1} - 2a\_{n+2} + 2$

$S\_n = a\_1 + a\_2 + \cdots + a\_n$이라 할 때, 병규는 $S\_n$을 빠르게 구하는 방법을 찾고 싶다. 병규를 위해 이 문제를 풀어주자.

첫째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 200\\,000)$

둘째 줄부터 $Q$개의 줄에 걸쳐 $n$이 주어진다. $(1 \leq n \leq 10^{18})$

입력으로 주어지는 모든 수는 정수이다.

각 줄에 $S\_n$을 한 줄에 하나씩 순서대로 출력한다.