Có lẽ bài toán đếm số lượng cặp nghiệm nguyên ~(x, y)~ không âm của phương trình ~ax+by=N~, với ~a, b, N~ cho trước đã rất quen thuộc với rất nhiều bạn. Tuy nhiên để giải bài toán với ~N~ lớn lại là một điều không hề dễ dàng chút nào. Ngày hôm nay, chúng ta thử thách với một bài toán khó hơn một chút: Đếm số lượng bộ ba ~(x, y, z)~ là nghiệm nguyên không âm của phương trình ~ax+by+cz=N~, với ~a, b, c~ và ~N~ cho trước.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~T~ là số lượng test của bài toán ~(T \leq 10)~.
• ~T~ dòng tiếp theo mỗi dòng chứa ~4~ số nguyên ~a, b, c~, và ~N~. ~\left(10^3 \leq a, b, c \leq 10^9 ; 0 \leq N \leq 10^9\right)~.

Kết quả:

• Ghi ra ~T~ dòng, mỗi dòng tương ứng là kết quả của mỗi test.

Ví dụ:

Sample Input

2 
1000 1000 1000 2000 
1000 1001 1002 10000

Sample Output

6
1

Giải thích:

Với test ví dụ 1: Ta có các ~6~ bộ thoả mãn ~(1, 1, 0), (1, 0, 1), (0, 1, 1), (2, 0, 0), (0, 2, 0), (0, 0, 2)~. Với test2 chỉ có duy nhất ~1~ bộ thoả mãn: ~(10,0,0)~.

Ràng buộc:

• Có ~40 \%~ số test với ~N \leq 10^6~;
• Có ~60\%~ số test còn lại có ~N \leq 10^6~.