Ване очень нравится математика. Однажды, когда он решал очередную задачу по математике, он придумал интересное дерево. Это дерево строится следующим образом.
Изначально в дереве есть только одна вершина с номером \(1\) — корень дерева. Затем, Ваня добавляет к ней двух детей, присваивая им последовательные номера — \(2\) и \(3\) соответственно. После этого, он будет добавлять детей к вершинам по возрастанию их номеров, начиная с \(2\), присваивая их детям минимальные не занятые номера. В итоге, у Вани получится бесконечное дерево с корнем в вершине \(1\), где каждая вершина будет иметь ровно два ребенка, а номера вершин будут расположены последовательно по слоям.
Часть дерева Вани. Ване стало интересно, чему равна сумма номеров вершин на пути от вершины с номером \(1\) до вершины с номером \(n\) в таком дереве. Так как Ваня не любит считать, он попросил Вас помочь ему узнать эту сумму.
Выходные данные
Для каждого набора входных данных выведите одно целое число — искомую сумму.
Примечание
В первом наборе данных примера на пути от корня до вершины \(3\) лежат две вершины \(1\) и \(3\), для них сумма равна \(4\).
Во втором наборе данных примера на пути от корня до вершины с номером \(10\) лежат вершины \(1\), \(2\), \(5\), \(10\), сумма их номеров равна \(1+2+5+10 = 18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
10
37
1
10000000000000000
15
|
4
18
71
1
19999999999999980
26
|