Các con gà trong trang trại Bedao đang ra sức phát triển và sinh nở. Mỗi con gà sẽ đẻ quả trứng đầu tiên vào thời điểm ~t~. Cứ sau ~k~ đơn vị thời gian con gà ấy sẽ tiếp tục đẻ trứng. Lihwy là chủ trang trại và anh ấy đang rất muốn quan tâm đến số lượng trứng thu được tại thời điểm ~n~. Hãy giúp Lihwy giải quyết bài toán trên nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~m~ ~(m \le 200)~ - số lượng con gà trong trang trại Bedao.

Mỗi dòng trong ~m~ dòng tiếp theo chứa ba số nguyên không âm ~t~, ~k~, ~n~ ~(0 \le t, n \le 10^{18}, 1 \le k \le 10^{18})~.

Output

Với mỗi con gà, hãy in ra số lượng quả trứng mà Lihwy thu được.

Scoring

Sample Input 1

5
0 1 1
1 1 1
1 1 0
0 1 0
0 2 2

Sample Output 1

2
1
0
1
2

Notes

Con gà thứ nhất đẻ trứng vào các thời điểm ~0~, ~1~, ~2~, ~3~, ... Tại thời điểm ~1~ ta sẽ thu được hai quả trứng.