Рассмотрим бесконечную последовательность \(s\) натуральных чисел, построенную повторением следующих шагов:
- Найдите лексикографически наименьшую тройку натуральных чисел \((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]\)
- Добавьте \(a\), \(b\), \(c\) в конец \(s\) в этом порядке.
- Вернитесь к первому шагу.
У вас есть целое число \(n\). Найдите \(n\)-й элемент \(s\).
Вы должны ответить на \(t\) независимых тестовых случаев.
Последовательность \(a\) лексикографически меньше последовательности \(b\), если в первой позиции, где \(a\) и \(b\) различны, в последовательности \(a\) элемент меньше, чем соответствующий элемент в \(b\).
Выходные данные
В каждой из строк \(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
|