Phần Tử Thứ K Ngoài Các Bội · canuc80k0512

Xét dãy tăng gồm tất cả số nguyên dương không chia hết cho $n$ . Với mỗi bộ test, hãy tìm phần tử thứ $k$ của dãy này, đánh số từ $1$ .

Input

Dòng đầu chứa số nguyên $t$ - số bộ test.
$t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $n$ và $k$ .

Output

Với mỗi bộ test, in số nguyên dương thứ $k$ không chia hết cho $n$ trên một dòng.

Constraints

$1 \leq t \leq 1000$ .
$2 \leq n \leq 1 0^{9}$ .
$1 \leq k \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50$ điểm): $t \leq 20, n, k \leq 1000$ .
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Khi $n = 4$ , tám số đầu tiên hợp lệ là $1, 2, 3, 5, 6, 7, 9, 10$ . Với $n = 100$ , trong các số từ $1$ đến $106$ chỉ có $100$ bị loại, nên $106$ là phần tử hợp lệ thứ $105$ .

Ý tưởng: Trong đoạn 1..x có floor(x/n) bội của n, nên số phần tử hợp lệ là x-floor(x/n). Đại lượng này không giảm theo x; đáp án là x nhỏ nhất làm số lượng đạt ít nhất k.
Ý tưởng: Ta chặt nhị phân trên [1,2k]. Cận phải luôn đủ vì trường hợp loại nhiều nhất là n=2, khi trong 2k số vẫn có đúng k số lẻ.
Ý tưởng: Tính đúng đắn: tại đáp án, đoạn 1..x chứa ít nhất k phần tử hợp lệ, còn 1..x-1 chứa ít hơn k. Do đó chính x là phần tử hợp lệ thứ k.
Ý tưởng: Độ phức tạp O(log k) mỗi bộ test và O(1) bộ nhớ.