Người ta vẽ ra \(n\) ô trống đánh số từ \(1\) tới \(n\) sau đó đặt đúng \(m\) viên sỏi vào trong ô trống thứ \(k\). Bạn được thực hiện thao tác: lấy một viên sỏi ở ô thứ \(k\) và chuyển nó sang một ô khác bất kỳ.
Yêu cầu: Hãy dùng ít thao tác nhất để rải các viên sỏi vào các ô, sao cho khi bạn kết thúc các thao tác, số sỏi trong hai ô liên tiếp bất kỳ chênh lệch nhau không quá \(1\). Cho biết số thao tác cần sử dụng

Input

Vào từ file văn bản ARRANGE.INP.

• Dòng 1 chứa số nguyên dương \(T \leq 10^5\) là số test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một test là ba số nguyên dương \(n, m, k\) cách nhau bởi dấu cách \((n ≤ 10^9; 𝑚 \leq 10^9; 1 \leq 𝑘 \leq 𝑛)\).

Output

• Ghi ra file văn bản ARRANGE.OUT.
• Ứng với mỗi test, ghi ra số thao tác cần sử dụng theo phương án tìm được

Example

2
4 8 3
5 6 5

5
3