숫자 찾기

Ujan은 청소에 지쳐서 잠시 쉬고 싶었고, 그래서 무한 수열을 가지고 놀기 시작했다. 그에게는 정수 $n$과 $k$가 있다. 그는 다음 단계를 반복해서 무한 수열 $s$를 만든다.

1. $s$에 없는 서로 다른 양의 정수 중 가장 작은 $k$개를 찾는다. 작은 수부터 차례로 $u_1, u_2, \ldots, u_k$라고 하자.
2. $u_1, u_2, \ldots, u_k$와 $\sum_{i=1}^{k} u_i$를 이 순서대로 $s$에 추가한다.
3. 첫 번째 단계로 돌아간다.

Ujan은 정수 $n$을 수열 $s$에 적는 순간 놀이를 그만둔다. $s_x = n$을 만족하는 인덱스 $x$를 구하라. 모든 양의 정수는 $s$에 정확히 한 번씩 등장함을 증명할 수 있다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^5$)가 주어진다.

이어서 $t$개의 줄에 정수 $n$과 $k$ ($1 \le n \le 10^{18}$, $2 \le k \le 10^6$)가 한 줄에 하나씩 주어진다.

각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.

첫 번째 예시에서 $s = (1, 2, 3, 4, 5, 9, 6, 7, 13, 8, 10, 18, \ldots)$이다. 여기서 $10$은 11번째 수이므로 답은 11이다.

두 번째 예시에서는 $s = (1, 2, 3, 4, 5, 15, 6, 7, 8, 9, 10, 40, \ldots)$이다.