交差判定

線分 s1, s2について、それらが交差する場合"1" 、しない場合"0"と出力してください。

s1 の端点を p0, p1、s2 の端点を p2, p3とします。

入力

１行目にクエリの数 q が与えられます。続く q 行に q 個のクエリが与えられます。 各クエリでは線分 s1、s2 の端点の座標が以下の形式で与えられます。

xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3

入力はすべて整数で与えられます。

出力

各クエリについて、"1" または"0"を１行に出力してください。

制約

• 1 ≤ q ≤ 1,000
• −10,000 ≤ x_pi, y_pi ≤ 10,000
• p0, p1 は同一でない。
• p2, p3 は同一でない。

入出力例

入力例 1

3
0 0 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0

出力例 1

1
1
0

Note

      解説      

---