Để tìm lại Bảy Viên Ngọc Rồng, Mabư Béo cần phải trải qua một hành trình dài, gian nan, khúc khuỷu.

Hắn đang cầm trên tay bản đồ của Vương quốc DTL hiện tại hắn đang đứng trên. Bản đồ có thể được thể hiện bởi mặt phẳng có trục tọa độ ~Oxy~, với vương quốc DTL trải dài theo hoành độ và tung độ, đều từ ~-10^4~ đến ~10^4~. Mỗi điểm ~(x, y)~ đều có một độ cao, được định nghĩa bởi hàm ~H(x, y)~. ~H(x, y)~ có dạng ~P(x) + Q(y)~. Trong đó: ~P(x)~ là một đa thức biến ~x~, có bậc tối đa là ~3~, và ~Q(y)~ là một đa thức biến ~y~, có bậc tối đa là ~3~.

Mabư Béo có thể tự do di chuyển trên thế giới này: đi bộ, leo trèo đến một vị trí gần vị trí hắn đang đứng, hay lên máy bay, hoặc dùng phép tele đến ở một vị trí rất xa, bất kỳ ở trong vương quốc DTL. Tất nhiên, hắn không muốn di chuyển ra ngoài vương quốc, vì hắn biết cả 7 viên Ngọc Rồng đều đang nằm đâu đó ở nơi này.

Tuy nhiên, vì không khí loãng, cùng nỗi sợ độ cao, hắn sẽ không thể tới thăm các điểm mà có độ cao bằng ~C~ hoặc hơn. Khi đó, tồn tại các "Vùng nguy hiểm" hắn đã vẽ ra trên hành trình của mình.

Cho mô tả của hàm ~H(x, y)~, hãy đếm xem có bao nhiêu Vùng nguy hiểm. Hai điểm được cho là cùng một vùng nguy hiểm nếu như tồn tại một đường đi bộ nối hai điểm với nhau, mà tất cả các điểm trên đường đi đó đều thuộc vùng nguy hiểm.

Input

Mỗi file test chứa nhiều trường hợp test. Dòng đầu của mỗi file chứa số trường hợp test trong file ~T~ (~1 \le T \le 10^5~). Mỗi trường hợp test được mô tả như sau:

• Dòng thứ nhất chứa ~4~ số nguyên: ~a_{x}~, ~b_{x}~, ~c_{x}~, ~d_{x}~ (~-100 \le a_x, b_x, c_x, d_x \le 100~) – thể hiện hàm ~P(x)~. ~P(x) = a_{x} \cdot x^3 + b_{x} \cdot x^2 + c_{x} \cdot x + d_{x}~.

• Dòng thứ hai chứa ~4~ số nguyên: ~a_{y}~, ~b_{y}~, ~c_{y}~, ~d_{y}~ (~-100 \le a_y, b_y, c_y, d_y \le 100~) – thể hiện hàm ~Q(y)~. ~Q(y) = a_{y} \cdot y^3 + b_{y} \cdot y^2 + c_{y} \cdot y + d_{y}~.

• Dòng thứ ba chứa số thực ~C~ (~|C| \le 10^{18}~).

Output

Với mỗi trường hợp test, in ra trên một dòng một số nguyên duy nhất: số Vùng nguy hiểm mà Mabư Béo không thể di chuyển đến.

Sample Input 1

2
0 1 0 0
0 1 0 0
200000000
1 1 1 1
-1 -1 -1 -1
0

Sample Output 1

4
1

Notes

Ở ví dụ đầu tiên, hàm ~H(x, y) = x^2 + y^2~. Mabư Béo không thể ghé thăm ~4~ góc ngoài cùng của vương quốc.