52. EXPLOSION!

題目敘述

熱愛爆裂魔法的惠惠，每天都在精進自己在爆裂魔法上的能力與成就。在施放爆裂魔法時大喊一聲「EXPLOSION!!!」更是大快人心。

最近，有一名不願透漏名字且舉止行為怪異、看起來就像變態的冒險者佐藤和真，告訴她可以到城鎮附近的樹林中，一座看起來像是廢棄的城堡練習爆裂魔法。在他們經過幾次的練習之後，卻發現城堡被可能還住在裡面的魔王軍幹部用魔法隱藏起來了！

不願透漏名字的冒險者和真和惠惠想憑著記憶找出城堡的位置，作為他們隊上的程式設計詩人，你能幫幫他們嗎?

樹林的地盤是一個二維座標平面。和真和惠惠腦海中有一些直線段，線段上的所有點就是城堡可能的所在位置。 他們想透過不停地放爆裂魔法瘋狂轟炸來來找出城堡的位置，但是受限於一天只能放一發爆裂魔法，惠惠只會對所有線段上的整數點放爆裂魔法。 給定所有的直線段的兩端點，請你幫他們找出所有在直線段上的整數點的數量。

保證所有直線段不會平行，也就是說，任兩條直線段最多只會有一個交點。

輸入

第一行有一個整數$n$，表示直線段的數量。 接下來有$n$行，每一行有四個整數$x_1、y_1、x_2、y_2$，$(x_1,y_1)、(x_2,y_2)$為一條直線段的兩端點。 $1\le n\le 10^3,\ -10^6\le x_1,y_1,x_2,y_2\le 10^6$

輸出

輸出所有直線段上的整數點的數量。

Sample I/O

Input

3
3 3 5 1
6 3 0 0
1 2 5 2

Output

10

說明

範例參考下圖:

測資限制

測資	範圍	配分
#1	同範測	20
#2	$1\le n\le 100,\ -10^3\le x_1,y_1,x_2,y_2\le 10^3$	20
#3	$1\le n\le 10^3,\ -10^3\le x_1,y_1,x_2,y_2\le 10^3$	20
#4	$1\le n\le 10^3,\ -10^6\le x_1,y_1,x_2,y_2\le 10^6$	20
#5	$1\le n\le 10^3,\ -10^6\le x_1,y_1,x_2,y_2\le 10^6$	20

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 5