Giáo sư X đang cần tiền đầu tư cho một dự án lớn. Số tiền cần có là ~n~ đồng nhưng tài khoản của ông đang có ~0~ đồng. Ông bèn đến ngân hàng và khóc... Bụt hiện lên dưới chức danh giám đốc ngân hàng hỏi "Vì sao con khóc?".

Sau khi nghe kể sự tình, Bụt bảo: "Được rồi, bây giờ mỗi ngày con có thể kiếm tiền nạp thêm vào tài khoản một số tiền tùy ý (có thể ~0~ đồng), rồi cuối ngày ta sẽ hô biến để số tiền trong tài khoản của con tăng lên gấp đôi. Tuy nhiên nếu có thời điểm tài khoản của con có nhiều hơn ~n~ đồng ta sẽ thu lại hết và tài khoản của con trở lại thành ~0~ đồng".

Yêu cầu: Giáo sư X chỉ có ~k~ ngày để huy động tiền, hãy cho biết số tiền ít nhất giáo sư X cần kiếm thêm để trong thời hạn đến hết ngày thứ ~k~, có thời điểm số tiền trong tài khoản của giáo sư X đúng bằng ~n~. Khi đó giáo sư X chỉ cần cảm ơn ông Bụt và rút hết ~n~ đồng ra đầu tư.

Input

• Dòng 1 chứa số nguyên dương ~T \le 10^5~ là số test.

• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~n, k \le 10^{18}~ cách nhau bởi dấu cách ứng với một test.

Output

• Ứng với mỗi test, ghi ra một số nguyên duy nhất trên một dòng là số tiền giáo sư X phải tự kiếm thêm để nạp vào tài khoản của mình.

Sample Input 1

4
10 2
99 5
123456789 9
999999999 100

Sample Output 1

3
8
482256
21

Notes

Test 1:

• Ngày 1: Giáo sư X nạp vào ~2~ đồng, cuối ngày có ~4~ đồng.

• Ngày 2: Giáo sư X nạp thêm ~1~ đồng, cuối ngày có ~10~ đồng.

Test 2:

• Ngày 1: Giáo sư X nạp vào ~6~ đồng, cuối ngày có ~12~ đồng.

• Ngày 2: Giáo sư X nạp thêm ~0~ đồng, cuối ngày có ~24~ đồng.

• Ngày 3: Giáo sư X nạp thêm ~0~ đồng, cuối ngày có ~48~ đồng.

• Ngày 4: Giáo sư X nạp thêm ~1~ đồng, cuối ngày có ~98~ đồng.

• Ngày 5: Giáo sư X nạp thêm ~1~ đồng thành ~99~ đồng.