수열과 병규

특이한 수열을 만드는 게 취미인 병규는 다음과 같은 수열 $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$을 한 줄에 하나씩 순서대로 출력한다.