Рассмотрим бесконечную последовательность \(s\) натуральных чисел, построенную повторением следующих шагов:
У вас есть целое число \(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 \)
9 1 2 3 4 5 6 7 8 9
1 2 3 4 8 12 5 10 15
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач