Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Trong dịp đầu năm mọi người thường Lì xì nhau để lấy may. Vậy cũng để lấy may cũng như cổ vũ tinh thầy làm việc của các nhân viên trong công ty. Giám đốc Kuro đã chỉ đạo xuống phòng kế toán của công ty thực hiện lì xì cho các nhân viên vào ngày đầu tiên đi làm.

Để tăng tính thú vị của ngày đầu năm thì công ty sẽ tổ chức cho các nhân viên 1 cuộc chơi các nhân viên sẽ lần lượt lên bốc mỗi lần bốc 1 viên bi. Mỗi viên bi chỉ có 1 màu duy nhất hoặc là đỏ hoặc là xanh hoặc là trắng.

Với từng màu nhân viên sẽ được hưởng các dịch vụ như sau:

• Nếu nhân viên bốc được viên bi màu đỏ thì nhân viên được công ty lì xì cho k $.
• Nếu nhân viên bốc được viên màu xanh thì công ty sẽ chúc nhân viên 1 lời chúc.
• Nếu nhân viên bốc được viên bi màu trắng nếu nhân viên có tiền trong tay thì phải lì xì lại công ty 1 $. nếu không có thì sẽ phải chúc công ty 1 lời chúc.

Được biết rằng tất cả nhân viên khi tham gia trò chơi này thì tất cả nhân viên đều không có đồng nào trên tay.

Cứ lần lượt như thế đến khi nào mà mỗi nhân viên có n viên bi trong tay.

Trong lúc chơi trò chơi thì giám đốc Kuro vi hành xuống sảnh nơi diễn ra trò chơi thì thấy không khí quá náo nhiệt giám đốc Kuro đã đố các nhân viên trong sảnh 1 câu đố ai giải được câu đố đó sẽ được nhận lì xì của giám đốc với giải thưởng trị giá 10 000 $. Câu hỏi là cần ít nhất bao nhiêu nhân viên để chắc chắn sau khi kết thúc n lượt chơi thì chắc chắn luôn tìm ra 2 nhân viên có cùng số tiền mà công ty đã lì xì.

Kun là 1 nhân viên trong công ty đó và cũng tham gia trò chơi nhưng Kun không biết sao trả lời được câu hỏi đó. Nhưng Kun đã nhanh trí nhớ ra rằng bạn là người rất giỏi trong việc giải những bài toán này. Hãy giúp Kun có được 10 000 $ bạn nhé !

Input

Số đầu tiên là số bộ test T (1 ≤ T ≤ 10⁵).

T dòng tiếp theo là 2 số n và k (1 ≤ k, n ≤ 10⁷).

Output

Mỗi bộ test in ra đáp án tương ứng.

Example

Input:
2
6 2
4 3

Output:
13
11