Một ngày đẹp trời, Hưng cùng những người bạn đến lớp của thầy Toàn. Vì muốn nâng cao trình độ cho học sinh của lớp này, Thầy quyết định ra một bài tập có độ khó là N. Nhưng sau khi ra đề cho học sinh, hầu như những người bạn của Hưng cảm thấy nó quá khó và đã phản hồi lại cho thầy Toàn. Chính vậy thầy Toàn đã quyết định chia bài tập có độ khó N này ra thành K bài toán có độ khó thấp hơn để các bạn học sinh có thể giải được. Độ khó cân bằng của toàn bộ bài mà thầy đã chia ra được tính bằng Ước chung lớn nhất của độ khó của K bài đó. Nhưng do thầy bận việc đột xuất, Thầy đã nhờ Hưng giúp thầy chia bài sao cho độ khó cân bằng phải là lớn nhất, Hưng đang làm dở những bài mà Hưng thích . Các bạn hãy giúp Hưng nhé!

Dữ liệu

Dòng đầu tiên là số nguyên dương Q là số lượng truy vấn

Q dòng tiếp theo là 2 số nguyên N và K là độ khó gốc của bài và số lượng bài cần chia ra

Kết quả

Q dòng là kết quả của từng truy vấn

Ràng buộc

Q<=\(10^3\),N<=\(10^8\) ,K<=N;

Input

3

10 3

5 5

420 69

Output

2

1

6

Giải thích

Đối với trường hợp thử nghiệm đầu tiên, một cách khả thi là chia nhỏ bài toán có độ khó 10 vào một bộ bài có ba bài toán khó 4,2 và 4 tương ứng, cho số dư bằng 2.

Đối với test case thứ 2, chỉ có một cách giải bài toán độ khó 5 vào một bộ vấn đề gồm 5 các vấn đề với mỗi vấn đề có độ khó 1 cho số dư bằng 1.