You are given $n$ segments on a Cartesian plane. Each segment's endpoints have integer coordinates. Segments can intersect with each other. No two segments lie on the same line.

Count the number of distinct points with integer coordinates, which are covered by at least one segment.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of segments.

Each of the next $n$ lines contains four integers $Ax_i, Ay_i, Bx_i, By_i$ ($-10^6 \le Ax_i, Ay_i, Bx_i, By_i \le 10^6$) — the coordinates of the endpoints $A$, $B$ ($A \ne B$) of the $i$-th segment.

It is guaranteed that no two segments lie on the same line.


-----Output-----

Print a single integer — the number of distinct points with integer coordinates, which are covered by at least one segment.


-----Examples-----
Input
9
0 0 4 4
-1 5 4 0
4 0 4 4
5 2 11 2
6 1 6 7
5 6 11 6
10 1 10 7
7 0 9 8
10 -1 11 -1

Output
42

Input
4
-1 2 1 2
-1 0 1 0
-1 0 0 3
0 3 1 0

Output
7



-----Note-----

The image for the first example: [Image] 

Several key points are marked blue, the answer contains some non-marked points as well.

The image for the second example: [Image]

Difficulty: interview

Starter code:

Solutions:
#      
import    sys 
 
def getIntList():
    return list(map(int, input().split()))    
 


 
N, = getIntList()

zp = []
for i in range(N):
    ax, ay, bx, by  = getIntList()
    if ax>bx:
        ax,bx = bx,ax
        ay,by = by, ay
    zp.append( (ax,ay, bx,by))
  
res = 0
def gcd(a,b): 
    if b==0:return a
    return gcd(b, a%b)
zgcd = []
for i in range(N):
    ax, ay, bx, by = zp[i]
    tx =  abs(bx-ax)
    ty = abs(by - ay)
 
    g = gcd(tx, ty)
    res += g+1
 
    zgcd .append(g)
 
"""
ax + k1 dax = bx + k2 dbx
ay + k1 day = by + k2 dby
"""
for i in range(N):
    ax = zp[i][0]
    dax = (zp[i][2] - ax) // zgcd[i]
    ay = zp[i][1]
    day = (zp[i][3] - ay) // zgcd[i]
    cross = []
    for j in range(i+1, N):
        #dprint('node',i,j)
        bx = zp[j][0]
        dbx = (zp[j][2] - bx) // zgcd[j]
        by = zp[j][1]
        dby = (zp[j][3] - by) // zgcd[j]
        #dprint(ax,dax,ay,day)
        #dprint(bx,dbx,by,dby)
        t1 = ax * day - ay * dax - bx * day + by * dax
        t2 = dbx *day - dby * dax
        
        #dprint(t1,t2)
        if t2==0:
            continue
        if t1%t2!=0:
            continue
        k2 = t1 // t2
        if k2 <0 or k2 > zgcd[j]:
            continue
        if dax!=0:
            t3 = k2*dbx + bx - ax
            if t3%dax!=0:
                continue
            k1 = t3//dax
        else:
            t3 = k2* dby + by - ay
            if t3%day !=0:
                continue
            k1 = t3//day
        if k1<0 or k1 > zgcd[i]:
            continue
        #dprint(ax + k1 * dax, ay+k1 * day)
        cross.append(k1)
    if not cross: continue
    cross.sort()
 
    d = 1
    for j in range(1, len(cross)):
        if cross[j]!=cross[j-1]:
            d+=1
    res-=d
print(res)
    





from math import gcd
from bisect import *

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y
    def __repr__(self):
        return 'Point' + repr((self.x, self.y))
    def __add__(self, val):
        return Point(self.x + val.x, self.y + val.y)
    def __sub__(self, val):
        return Point(self.x - val.x, self.y - val.y)
    def __mul__(self, ratio):
        return Point(self.x * ratio, self.y * ratio)

    @staticmethod
    def det(A, B):
        return A.x * B.y - A.y * B.x
    @staticmethod
    def dot(A, B):
        return A.x * B.x + A.y * B.y

    def onSegment(self, A, B):
        if self.det(B-A, self-A) != 0:
            return False
        if self.dot(B-A, self-A) < 0:
            return False
        if self.dot(A-B, self-B) < 0:
            return False
        return True
        

def intPoints(x1, y1, x2, y2):
    dx, dy = abs(x2 - x1), abs(y2 - y1)
    return gcd(dx, dy) + 1

def crosspoint(L1, L2):
    A, B = Point(L1[0], L1[1]), Point(L1[2], L1[3])
    C, D = Point(L2[0], L2[1]), Point(L2[2], L2[3])
    S1, S2 = Point.det(C-A, D-A), Point.det(C-D, B-A)
    delta = (B - A) * S1
    if S2 == 0 or delta.x % S2 != 0 or delta.y % S2 != 0:
        return None
    delta.x = delta.x // S2
    delta.y = delta.y // S2
    P = A + delta
    if not P.onSegment(A, B) or not P.onSegment(C, D):
        return None
    return (P.x, P.y)
'''
while True:
    x1, y1, x2, y2 = map(int, input().split())
    A, B = Point(x1, y1), Point(x2, y2)
    x1, y1, x2, y2 = map(int, input().split())
    C, D = Point(x1, y1), Point(x2, y2)
    print(crosspoint(A, B, C, D))
'''

n = int(input())
lines = [ tuple(int(z) for z in input().split()) \
          for i in range(n) ]
count = dict()
for i in range(n):
    for j in range(i):
        P = crosspoint(lines[i], lines[j])
        if P == None:
            continue
        if not P in count:
            count[P] = 1
        else:
            count[P] += 1


answer = sum(intPoints(*L) for L in lines)
tri = [ x*(x+1)//2 for x in range(n+1) ]
for z in count:
    k = bisect_right(tri, count[z])
    answer -= k - 1;
print(answer)


from math import gcd
from bisect import *

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y
    def __add__(self, val):
        return Point(self.x + val.x, self.y + val.y)
    def __sub__(self, val):
        return Point(self.x - val.x, self.y - val.y)
    def __mul__(self, ratio):
        return Point(self.x * ratio, self.y * ratio)
    def __truediv__(self, ratio):
        return Point(self.x / ratio, self.y / ratio)

    @staticmethod
    def det(A, B):
        return A.x * B.y - A.y * B.x
    @staticmethod
    def dot(A, B):
        return A.x * B.x + A.y * B.y

    def onSegment(self, A, B):
        if self.det(B-A, self-A) != 0:
            return False
        if self.dot(B-A, self-A) < 0:
            return False
        if self.dot(A-B, self-B) < 0:
            return False
        return True
        

def intPoints(x1, y1, x2, y2):
    dx, dy = abs(x2 - x1), abs(y2 - y1)
    return gcd(dx, dy) + 1

def crosspoint(L1, L2):
    A, B = Point(L1[0], L1[1]), Point(L1[2], L1[3])
    C, D = Point(L2[0], L2[1]), Point(L2[2], L2[3])
    S1, S2 = Point.det(C-A, D-A), Point.det(C-D, B-A)
    delta = (B - A) * S1
    if S2 == 0 or delta.x % S2 != 0 or delta.y % S2 != 0:
        return None
    delta = delta / S2;
    P = A + delta
    if not P.onSegment(A, B) or not P.onSegment(C, D):
        return None
    return (P.x, P.y)

n = int(input())
lines = [ tuple(int(z) for z in input().split()) \
          for i in range(n) ]
count = dict()
for i in range(n):
    for j in range(i):
        P = crosspoint(lines[i], lines[j])
        if P != None:
            count[P] = count.get(P, 0) + 1

answer = sum(intPoints(*L) for L in lines)
tri = [ x*(x+1)//2 for x in range(n+1) ]
for z in count:
    k = bisect_right(tri, count[z])
    answer -= k - 1;
print(answer)


import sys
from math import gcd


class Segment:
    def __init__(self, x1, y1, x2, y2):
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
    
    def dx(self):
        return self.x2 - self.x1
    
    def dy(self):
        return self.y2 - self.y1
    
    def pt_cnt(self):
        return gcd(abs(self.dx()), abs(self.dy())) + 1
    
    def A(self):
        return self.y1 - self.y2
    
    def B(self):
        return self.x2 - self.x1

    def C(self):
        return -self.A() * self.x1 - self.B() * self.y1

    def inner_x(self, x):
        l = self.x1
        r = self.x2
        if l > r:
            l, r = r, l
        return l <= x <= r
    
    def inner_y(self, y):
        l = self.y1
        r = self.y2
        if l > r:
            l, r = r, l
        return l <= y <= r
    
    def inner(self, x, y):
        return self.inner_x(x) and self.inner_y(y)

    def intersect(self, other):
        dx = det(self.C(), self.B(), other.C(), other.B())
        dy = det(self.A(), self.C(), other.A(), other.C())
        d = det(self.A(), self.B(), other.A(), other.B())
        if d == 0:
            return False, 0, 0
        if dx % d != 0 or dy % d != 0:
            return False, 0, 0
        x = -dx // d
        y = -dy // d
        if not self.inner(x, y) or not other.inner(x, y):
            return False, 0, 0
        return True, x, y


def det(a, b, c, d):
    return a * d - b * c

def main():
    n = int(input())
    segments = []
    ans = 0
    for _ in range(n):
        x1, y1, x2, y2 = map(int, input().split())
        segment = Segment(x1, y1, x2, y2)
        ans += segment.pt_cnt()
        pt = set()
        for other in segments:
            result, x, y = segment.intersect(other)
            if result:
                pt.add((x, y))
        ans -= len(pt)
        segments.append(segment)  
    print(ans)
        
def __starting_point():
    main()
__starting_point()

from math import gcd
n=int(input());
pts=[]
ans=0
for i in range(0,n):
	a,b,A,B=tuple(map(int,input().split(' ')))
	pts.append((a,b,A,B))
	ans+=(gcd(abs(a-A),abs(b-B))+1)
m=dict()
for i in range(n):
	for j in range(i+1,n):
		a1=pts[i][0]
		b1=pts[i][1]
		a2=pts[i][2]
		b2=pts[i][3]
		A1=pts[j][0]
		B1=pts[j][1]
		A2=pts[j][2]
		B2=pts[j][3]
		num1=(b2-B2)*(A2-A1)*(a2-a1)+A2*(a2-a1)*(B2-B1)-a2*(A2-A1)*(b2-b1)
		den1=(B2-B1)*(a2-a1)-(b2-b1)*(A2-A1)
		if(den1!=0 and num1%den1==0):
			if(a1==a2):
				num2=B2*(A2-A1)+(num1//den1-A2)*(B2-B1)
				den2=(A2-A1)
				if(num2%den2==0):
					if((num1//den1-A2)*(num1//den1-A1)<=0 and (num2//den2-B2)*(num2//den2-B1)<=0 and (num1//den1-a2)*(num1//den1-a1)<=0 and (num2//den2-b2)*(num2//den2-b1)<=0):
						if((num1//den1,num2//den2) not in m):
							m[(num1//den1,num2//den2)]=set();
						m[(num1//den1,num2//den2)].add(i);
						m[(num1//den1,num2//den2)].add(j);
			else:
				num2=b2*(a2-a1)+(num1//den1-a2)*(b2-b1);
				den2=(a2-a1);
				if(num2%den2==0):
					if((num1//den1-A2)*(num1//den1-A1)<=0 and (num2//den2-B2)*(num2//den2-B1)<=0 and (num1//den1-a2)*(num1//den1-a1)<=0 and (num2//den2-b2)*(num2//den2-b1)<=0):
						if((num1//den1,num2//den2) not in m):
							m[(num1//den1,num2//den2)]=set();
						m[(num1//den1,num2//den2)].add(i);
						m[(num1//den1,num2//den2)].add(j);
sum=0
for i in list(m.values()):
	sum+=(len(i)-1)
print(ans-sum)


# -*- coding: utf-8 -*-
"""
Created on Tue Sep 18 10:09:57 2018

@author: a.teffal

Chalenge :  Covered Points
"""


from math import gcd

def covered_points(xa, ya, xb, yb):
    '''
    assumes all parameters are integers
    Returns the covered points by the segement A-B having integer 
    coordinates
    
    '''
    
    #this just to have A in the left and B in the right
    if xb < xa :
        temp_x = xa
        xa = xb
        xb = temp_x
        
        temp_y = ya
        ya = yb
        yb = temp_y
    
    y_0 = abs(yb - ya)
    x_0 = xb - xa
    
    #pgdc_y_x = gcd(y_0, x_0)
    
    return gcd(y_0, x_0) + 1

def intersection2(xa, ya, xb, yb, xc, yc, xd, yd):
    
    
    if max(xa, xb) < min(xc,xd):
        return ()
    
    if max(ya, yb) < min(yc,yd):
        return ()
    
    # if both A-B and C - D ara parallel to x-axis
    # then no intersection (it is garanted that no segments lie on the same line)
    if (xa == xb and xc == xd) or (ya == yb and yc == yd):
        return ()
    if ya == yb and yc == yd:
        return ()
    
    
    
    
    a1 = yb - ya
    b1 = xb - xa
    #c1 = xa*(yb - ya) - ya*(xb - xa)
    c1 = xa*a1 - ya*b1
    
    a2 = yd - yc
    b2 = xd - xc
    #c2 = xc*(yd - yc) - yc*(xd - xc)
    c2 = xc*a2 - yc*b2
    
    det = a1 * b2 - a2 * b1
    
    if det == 0:
        return ()
    
    detx = c1 * b2 - c2 * b1
    
    dety = -a1 * c2 + a2 * c1
    
    if (detx % det) != 0 or (dety % det) !=0 :
        return ()
    
    x = int(detx/det)
    y = int(dety/det)
    
    if x < min(xa, xb) or x > max(xa, xb) or x < min(xc, xd) or x > max(xc, xd) :
        return ()
    if y < min(ya, yb) or y > max(ya, yb) or y < min(yc, yd) or y > max(yc, yd) :
        return ()
    
    return (x, y)
    

def __starting_point():
    #number of segments
    n = int(input())
    
    #initiate lists of point coordinates
    Ax = [0]*n
    Ay = [0]*n
    Bx = [0]*n
    By = [0]*n
    
    
    
    n_cov = 0
    intersections = {}
    
    #counting covered by each segment
    for i in range(n):
        line = input().split(sep = ' ')
        Ax[i] = int(line[0])
        Ay[i] = int(line[1])
        Bx[i] = int(line[2])
        By[i] = int(line[3])
        n_cov += covered_points(Ax[i], Ay[i], Bx[i], By[i])
    
    
    #substructing reapted points (intersection)
    for i in range(n):
        for j in range(i+1, n):
            temp = intersection2(Ax[i], Ay[i], Bx[i], By[i], Ax[j], Ay[j], Bx[j], By[j])
            if len(temp)==0:
                continue
            if temp in intersections:
                intersections[temp].append(i)
                intersections[temp].append(j)
            else:
                intersections[temp] = [i, j]
                
    for i in intersections:
        n_cov = n_cov - len(set(intersections[i])) + 1
        
    print(n_cov)

    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

__starting_point()


def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
    

def line_intersection(line1, line2):
    px, py, qx, qy = line1
    rx, ry, sx, sy = line2
    
    xdiff = (px - qx, rx - sx)
    ydiff = (py - qy, ry - sy)

    div = cross(px - qx, rx - sx, py - qy, ry - sy)
    if div == 0:
      raise Exception('lines do not intersect')

    pq, rs = cross(px, py, qx, qy), cross(rx, ry, sx, sy)
    x = cross(pq, rs, px - qx, rx - sx) / div
    y = cross(pq, rs, py - qy, ry - sy) / div
    return x, y
    
def online(line, x, y):
    a, b, c, d = line
    if min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):
        return True
    else:
        return False



def CF1036E():
    N = int(input())
    lines = []
    count = 0
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        points = gcd(abs(x1 - x2), abs(y1 - y2)) + 1
        count += points
        lines.append((x1, y1, x2, y2))
    for i in range(N):
        d = set()
        for j in range(i+1, N):
            px = lines[i][0]
            py = lines[i][1]
            qx = lines[j][0]
            qy = lines[j][1]
            rx = lines[i][2] - lines[i][0]
            ry = lines[i][3] - lines[i][1]
            sx = lines[j][2] - lines[j][0]
            sy = lines[j][3] - lines[j][1]

            rs = cross(rx, ry, sx, sy)
            # qpr = cross(qx - px, qy - py, rx, ry)
            
            if rs == 0: continue
        
            # qpr = cross(qx - px, qy - py, rx, ry)
            # qps = cross(qx - px, qy - py, sx, sy)
            # t = qps / rs
            # u = qpr / rs
            x, y = line_intersection(lines[i], lines[j])
            if not (x % 1 == 0 and y % 1 == 0): continue
            if not (online(lines[i], x, y) and online(lines[j], x, y)): continue
            d.add((x, y))
            
        count = count - len(d)
        
    return int(count)
    
def __starting_point():
    res = CF1036E()
    print(res)
__starting_point()

'''

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

'''
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
    

def online(line, x, y):
    a, b, c, d = line
    if min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):
        return True
    else:
        return False


def CF1036E():
    N = int(input())
    lines = []
    count = 0
    
    # Find the lines covered by each line segment
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        count += gcd(abs(x1 - x2), abs(y1 - y2)) + 1
        lines.append((x1, y1, x2, y2))
        
    # Deal with the intersecting points
    for i in range(N):
        d = set()
        for j in range(i+1, N):
            px, py, qx, qy = lines[i]
            rx, ry, sx, sy = lines[j]
            
            line1p = (px - qx, rx - sx)
            line2p = (py - qy, ry - sy)
            
            # Cross of two lines        
            area = cross(line1p[0], line1p[1], line2p[0], line2p[1])
        
            # Parallel line has no intersection            
            if area == 0: continue

            lineA = cross(px, py, qx, qy)
            lineB = cross(rx, ry, sx, sy)
            x = cross(lineA, lineB, line1p[0], line1p[1]) / area
            y = cross(lineA, lineB, line2p[0], line2p[1]) / area

            # Verify the points are good
            if not (x % 1 == 0 and y % 1 == 0): continue
            if not (online(lines[i], x, y) and online(lines[j], x, y)): continue
    
            d.add((x, y))
            
        count -= len(d)
        
    return count
    
def __starting_point():
    res = CF1036E()
    print(res)
__starting_point()

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
    

def online(line, x, y):
    a, b, c, d = line
    if min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):
        return True
    else:
        return False


def CF1036E():
    N = int(input())
    lines = []
    count = 0
    
    # Find the lines covered by each line segment
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        count += gcd(abs(x1 - x2), abs(y1 - y2)) + 1
        lines.append((x1, y1, x2, y2))
        
    # Deal with the intersecting points
    for i in range(N):
        d = set()
        for j in range(i+1, N):
            px, py, qx, qy = lines[i]
            rx, ry, sx, sy = lines[j]
            
            vecx = (px - qx, rx - sx)
            vecy = (py - qy, ry - sy)
            
            # Cross of two lines        
            area = cross(vecx[0], vecx[1], vecy[0], vecy[1])
        
            # Parallel line has no intersecting points            
            if area == 0: continue
            
            # Computation of the exact point
            # This has been referenced from : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
            lineA = cross(px, py, qx, qy)
            lineB = cross(rx, ry, sx, sy)
            x = cross(lineA, lineB, vecx[0], vecx[1]) / area
            y = cross(lineA, lineB, vecy[0], vecy[1]) / area

            # Verify the points are good. 
            # If the points are integers and lie of the lines they are valid.
            if not (x % 1 == 0 and y % 1 == 0): continue
            if not (online(lines[i], x, y) and online(lines[j], x, y)): continue
    
            d.add((x, y))
            
        count -= len(d)
        
    return count
    
def __starting_point():
    res = CF1036E()
    print(res)
__starting_point()

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
    

def online(line, x, y):
    a, b, c, d = line
    if min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):
        return True
    return False


def CF1036E():
    N = int(input())
    lines = []
    count = 0
    
    # Find the lines covered by each line segment
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        count += gcd(abs(x1 - x2), abs(y1 - y2)) + 1
        lines.append((x1, y1, x2, y2))
        
    # Deal with the intersecting points
    for i in range(N):
        d = set()
        for j in range(i+1, N):
            px, py, qx, qy = lines[i]
            rx, ry, sx, sy = lines[j]
            
            vecx = (px - qx, rx - sx)
            vecy = (py - qy, ry - sy)
            
            # Cross of two lines        
            area = cross(vecx[0], vecx[1], vecy[0], vecy[1])
        
            # Parallel line has no intersecting points            
            if area == 0: continue
            
            # Computation of the exact point
            # This has been referenced from : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
            lineA = cross(px, py, qx, qy)
            lineB = cross(rx, ry, sx, sy)
            x = cross(lineA, lineB, vecx[0], vecx[1]) / area
            y = cross(lineA, lineB, vecy[0], vecy[1]) / area

            # Verify the points are good. 
            # If the points are integers and lie of the lines they are valid.
            if not (x % 1 == 0 and y % 1 == 0): continue
            if not (online(lines[i], x, y) and online(lines[j], x, y)): continue
    
            d.add((x, y))
            
        count -= len(d)
        
    return count
    
def __starting_point():
    res = CF1036E()
    print(res)
__starting_point()

# Borrows primarily from : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
    

def online(line, x, y):
    a, b, c, d = line
    if min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):
        return True
    return False


def CF1036E():
    N = int(input())
    lines = []
    count = 0
    
    # Find the lines covered by each line segment
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        count += gcd(abs(x1 - x2), abs(y1 - y2)) + 1
        lines.append((x1, y1, x2, y2))
        
    # Deal with the intersecting points
    for i in range(N):
        d = set()
        for j in range(i+1, N):
            px, py, qx, qy = lines[i]
            rx, ry, sx, sy = lines[j]
            
            vecx = (px - qx, rx - sx)
            vecy = (py - qy, ry - sy)
            
            # Cross of two lines        
            area = cross(vecx[0], vecx[1], vecy[0], vecy[1])
        
            # Not interested in overlapping parallel lines
            if area == 0: continue
            
            # Computation of the exact point
            # This has been referenced from : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
            lineA = cross(px, py, qx, qy)
            lineB = cross(rx, ry, sx, sy)
            x = cross(lineA, lineB, vecx[0], vecx[1]) / area
            y = cross(lineA, lineB, vecy[0], vecy[1]) / area

            # Verify the points are good. 
            # If the points are integers and lie of the lines they are valid.
            if not (x % 1 == 0 and y % 1 == 0): continue
            if not (online(lines[i], x, y) and online(lines[j], x, y)): continue
    
            d.add((x, y))
            
        count -= len(d)
        
    return count
    
def __starting_point():
    res = CF1036E()
    print(res)
__starting_point()

""" 
1036E : Covered Points 
Borrows primarily from : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
"""

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
    

def online(line, x, y):
    """ If the x and y are within the range of min and max of x and y's respectively 
    then the points MAY lie on the line
    """
    a, b, c, d = line
    if min(a, c) <= x <= max(a, c) and min(b, d) <= y <= max(b, d):
        return True
    return False


def CF1036E():
    N = int(input())
    
    lines = []
    count = 0
    # Read input line segment and find the lines covered by each line segment
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        count += gcd(abs(x1 - x2), abs(y1 - y2)) + 1
        lines.append((x1, y1, x2, y2))
        
    # Deal with the intersecting points
    for i in range(N):
        d = set()  # Unique intersecting points
        for j in range(i+1, N):
            px, py, qx, qy = lines[i]
            rx, ry, sx, sy = lines[j]
            
            vecx = (px - qx, rx - sx)
            vecy = (py - qy, ry - sy)
            
            # Cross of two lines        
            area = cross(vecx[0], vecx[1], vecy[0], vecy[1])
        
            # Parallel line has no intersecting points            
            if area == 0: continue
            
            # Computation of the exact point
            # This has been referenced from : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
            lineA = cross(px, py, qx, qy)
            lineB = cross(rx, ry, sx, sy)
            x = cross(lineA, lineB, vecx[0], vecx[1]) / area
            y = cross(lineA, lineB, vecy[0], vecy[1]) / area

            # Verify the points are good. 
            # If the points are integers and lie of the lines they are valid.
            if not (x % 1 == 0 and y % 1 == 0): continue
            if not (online(lines[i], x, y) and online(lines[j], x, y)): continue
    
            d.add((x, y))
            
        count -= len(d)
        
    return count
    
def __starting_point():
    res = CF1036E()
    print(res)
__starting_point()