Cho hai số nguyên dương ~n~ và ~k~.

Hãy xây dựng một dãy số có nhiều phần tử nhất, giả sử dãy có ~x~ phần tử, dãy cần thỏa mãn:

• ~\sum a_i = n~.
• ~a_i > 0~.
• Không có tập con nào của dãy có tổng bằng đúng ~k~.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 200~) là số lượng test.

Mỗi test gồm hai số nguyên dương ~n, k~ (~1 \le n \le 10^{18}, 1 \le k \le 8~).

Output

~T~ dòng, mỗi dòng là số phần tử lớn nhất tìm được.

Nếu không có dãy nào thỏa mãn, in ra ~-1~.

Sample Input

3
5 2
7 3
8 1

Sample Output

2
3
4

Trong test đầu tiên, dãy là ~[1, 4]~.

Trong test thứ hai, dãy là ~[1, 1, 5]~.

Trong test thứ ba, dãy là ~[2, 2, 2, 2]~.