Thỏ là một vận động viên Olympic nhảy đường dài. Cuộc thi còn cách hơn một tháng nữa, huấn luyện viên Rùa muốn cậu cố gắng tập luyện chăm chỉ hơn. Sân chạy của Thỏ là một vòng tròn có độ dài \(L\), mỗi bước Thỏ chỉ nhảy từ vị trí hiện tại đến vị trí tiếp theo có khoảng cách là \(K\) theo chiều kim đồng hồ.

Sau khi tập được một lúc, Thỏ lười biếng tỏ ra mệt mỏi và không muốn tập luyện nữa. Thấy vậy, Rùa cho phép Thỏ có thể nghỉ ngơi với điều kiện là nếu cậu có thể nhảy từ vị trí hiện tại đến đúng điểm xuất phát thì buổi tập sẽ kết thúc. Thỏ nghe vậy thì rất khoái chí và đồng ý ngay lập tức. Biết rằng vào lúc đó thỏ cách vị trí xuất phát một độ dài \(S\) theo chiều kim đồng hồ.

Hãy tính toán sau ít nhất bao nhiêu lần nhảy Thỏ mới có thể đến được điểm xuất phát. Nếu Thỏ không có cách nào để nhảy đến vị trí xuất phát, in ra \(-1\).

Input

• Dòng đầu tiên chứa một số nguyên \(T\) \((1 \leq T \leq 100)\) \(-\) số lượng test case.
• \(T\) dòng tiếp theo, mỗi dòng là dữ liệu ứng với một test case, dòng thứ \(i\) chứa ba số nguyên \(L, S, K\) \((1 \leq S < L \leq 10^9, \ 1 \leq K \leq 10^9)\) ứng với test case thứ \(i\).

Output

• Với mỗi test case, in ra kết quả theo yêu cầu trên từng dòng.

Example

4
10 4 3
1000 11 2
998244353 897581057 595591169
10000 6 14

2
-1
249561088
3571