Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy ý: chọn một số nguyên x từ 1 đến k và trừ x khỏi n.

Nếu giá trị hiện tại của n là số chẵn thì bạn chỉ được trừ một số chẵn. Nếu giá trị hiện tại của n là số lẻ thì bạn chỉ được trừ một số lẻ.

Hãy tính số thao tác tối thiểu cần thiết để biến n thành 0.

Input

Dòng đầu tiên là số nguyên t (1 ≤ t ≤ 10000) — số lượng bộ test.

Mỗi test gồm một dòng chứa hai số nguyên n và k (3 ≤ k ≤ n ≤ 10⁹, k là số lẻ).

Output

Với mỗi test, in ra một số nguyên — số thao tác tối thiểu để biến n thành 0.

Ví dụ

Input
8
39 7
9 3
6 3
999967802 3
5 5
6 5
999999999 3
1000000000 3

Output
7
4
3
499983901
1
2
499999999
500000000