Олимпиадный тренинг

Задача . C. Прекрасные тройки


Рассмотрим бесконечную последовательность \(s\) натуральных чисел, построенную повторением следующих шагов:

  1. Найдите лексикографически наименьшую тройку натуральных чисел \((a, b, c)\) такую, ​​что Здесь тройка целых чисел \((a_1, b_1, c_1)\) считается лексикографически меньше тройки \((a_2, b_2, c_2)\), если последовательность \([a_1, b_1, c_1]\) лексикографически меньше последовательности \([a_2, b_2, c_2]\)
  2. Добавьте \(a\), \(b\), \(c\) в конец \(s\) в этом порядке.
  3. Вернитесь к первому шагу.

У вас есть целое число \(n\). Найдите \(n\)-й элемент \(s\).

Вы должны ответить на \(t\) независимых тестовых случаев.

Последовательность \(a\) лексикографически меньше последовательности \(b\), если в первой позиции, где \(a\) и \(b\) различны, в последовательности \(a\) элемент меньше, чем соответствующий элемент в \(b\).

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^5\))  — количество тестовых случаев.

Каждая из следующих \(t\) строк содержит одно целое число \(n\) (\(1\le n \le 10^{16}\))  — позицию элемента, который вы хотите узнать.

Выходные данные

В каждой из строк \(t\) выведите ответ на соответствующий тестовый случай.

Примечание

Первые несколько элементов \(s\) это \(1, 2, 3, 4, 8, 12, 5, 10, 15, \dots \)


Примеры
№Входные данныеВыходные данные
1
9
1
2
3
4
5
6
7
8
9
1
2
3
4
8
12
5
10
15
Статистика успешных решений по компиляторам
 Кол-во
С++4