D. Нахождение числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Уджану нужен перерыв от уборки, поэтому он начал играться с бесконечными последовательностями. У него есть два числа $$$n$$$ и $$$k$$$. Он создаёт бесконечную последовательность $$$s$$$, повторяя следующие шаги.

  1. Находятся $$$k$$$ наименьших различных положительных целых чисел, которые не появляются в $$$s$$$. Назовём их $$$u_{1}, u_{2}, \ldots, u_{k}$$$ от наименьшего до наибольшего.
  2. Числа $$$u_{1}, u_{2}, \ldots, u_{k}$$$ и $$$\sum_{i=1}^{k} u_{i}$$$ дописываются в таком порядке в конец $$$s$$$.
  3. Процесс переходит назад на первый шаг и повторяется.

Уджан прекратит валять дурака, когда он запишет число $$$n$$$ в последовательности $$$s$$$. Помогите ему найти позицию $$$n$$$ в $$$s$$$. Другими словами, найдите целое число $$$x$$$ такое, что $$$s_{x} = n$$$. Возможно доказать, что все положительные целые числа появляются в $$$s$$$ ровно по одному разу.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^{5}$$$), количество тестовых примеров.

Затем каждая из следующих $$$t$$$ строк содержит по два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le k \le 10^{6}$$$), число, которое необходимо найти в последовательности $$$s$$$ и параметр для создания самой последовательности $$$s$$$.

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

В каждой из $$$t$$$ строк выведите ответ на соответствующий тестовый пример.

Пример
Входные данные
2
10 2
40 5
Выходные данные
11
12
Примечание

В первом примере, $$$s = (1, 2, 3, 4, 5, 9, 6, 7, 13, 8, 10, 18, \ldots)$$$. $$$10$$$ является $$$11$$$-th по счёту числом, поэтому ответ $$$11$$$.

Во втором примере, $$$s = (1, 2, 3, 4, 5, 15, 6, 7, 8, 9, 10, 40, \ldots)$$$.