An đang học về số học, anh ta gặp bài toán sau.

Một cây rút tiền tự động ATM có 2 loại tiền mệnh giá \(a\) đồng và \(b\) đồng. Một khách hàng muốn rút số tiền là \(c\) đồng. Hỏi có bao nhiêu cách khác nhau để cây ATM này trả cho khách hàng.

Hai cách được coi là khác nhau nếu số tờ tiền loại mệnh giá \(a\) đồng hoặc \(b\) đồng là khác nhau trong hai cách. Giả thiết số tiền mỗi loại đủ nhiều để trả cho mọi cách.

Yêu cầu Bạn hãy giúp An giải bài toán trên.

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) là số bộ dữ liệu.
• Mỗi dòng trong \(T\) dòng tiếp theo mô tả một bộ dữ liệu, bao gồm 3 số nguyên \(a, b\) và \(c\) (\(1 \le a, b, c \le 10^9, a \ne b\)).

Output

• Với mỗi bộ dữ liệu, ghi ra trên một dòng câu trả lời.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le T \le 10, 1 \le a, b, c \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): Như ràng buộc trong đề bài.

Example

2
2 3 8
10 4 6

2
0