Nối tiếp bài WATER - Đổ nước của admin thì hôm nay Siro muốn mở rộng đề bài ra như sau:

Trong một đài phun nước, bạn có ~2~ chiếc bình dung tích ~a, b~ lít. Ban đầu ~2~ chiếc bình đều không chứa nước. Bạn chỉ được sử dụng ~2~ chiếc bình ~a~ và ~b~. Hãy cho biết số bước lấy được chính xác ~c~ lít nước.

Lưu ý: Bạn chỉ được sử dụng hai chiếc bình khi thõa mãn một trong các điều kiện sau:

• Đổ đầy nước vào bình,
• Làm trống bình nước,
• Bình được đổ phải đầy nước hoặc bình đổ qua phải hết.

Yêu cầu: Bạn hãy trả lời ~T~ câu hỏi dạng cho biết số bước tối thiểu để lấy đúng ~c~ lít bằng cách sử dùng bình ~a, b~ theo quy tắc trên.

Input

Dòng đầu chứa số nguyên dương ~T (1 \le T \le 100)~ là số lượng câu hỏi;

~T~ dòng tiếp theo, dòng thứ ~i~ là câu hỏi ~i~ có ~3~ số nguyên dương ~a, b, c (1 \le a, b, c \le 100)~.

Output

Ghi ra trên ~T~ dòng, dòng thứ ~i~ là đáp án câu hỏi ~i~, ghi số bước để lấy được ~c~ lít, ghi ~-1~ nếu không thể lấy được ~c~ lít.

Sample

Input #1

2
3 5 4
3 6 4

Output #1

6
-1

Hint

• Câu hỏi 1:
• Bước ~1: a = 0, b = 5~
• Bước ~2: a = 3, b = 2~
• Bước ~3: a = 0, b = 2~
• Bước ~4: a = 2, b = 0~
• Bước ~5: a = 2, b = 5~
• Bước ~6: a = 3, b = 4~