description: This is the hard version of the problem. The only difference from the easy version is that in this version the coordinates can be both odd and even.
  
  There are n fence-posts at distinct coordinates on a plane. It is guaranteed that no three fence posts lie on the same line.
  
  There are an infinite number of cows on the plane, one at every point with integer coordinates.
  
  Gregor is a member of the Illuminati, and wants to build a triangular fence, connecting 3 distinct existing fence posts. A cow strictly inside the fence is said to be enclosed. If there are an odd number of enclosed cows and the area of the fence is an integer, the fence is said to be interesting.
  
  Find the number of interesting fences.
  
  Input
  
  The first line contains the integer n (3 ≤ n ≤ 6000), the number of fence posts which Gregor can choose to form the vertices of a fence.
  
  Each of the next n line contains two integers x and y (0 ≤ x,y ≤ 10^7, where (x,y) is the coordinate of a fence post. All fence posts lie at distinct coordinates. No three fence posts are on the same line.
  
  Output
  
  Print a single integer, the number of interesting fences. Two fences are considered different if they are constructed with a different set of three fence posts.
  
  Examples
  
  Input
  
  
  3
  0 0
  2 0
  0 4
  
  
  Output
  
  
  1
  
  
  Input
  
  
  4
  1 8
  0 6
  5 2
  5 6
  
  
  Output
  
  
  1
  
  
  Input
  
  
  10
  170 59
  129 54
  5 98
  129 37
  58 193
  154 58
  24 3
  13 138
  136 144
  174 150
  
  
  Output
  
  
  29
  
  Note
  
  In the first example, there is only 1 fence. That fence is interesting since its area is 4 and there is 1 enclosed cow, marked in red.
  
  <image>
  
  In the second example, there are 4 possible fences. Only one of them is interesting however. That fence has an area of 8 and 5 enclosed cows.
  
  <image>
solution: #include <bits/stdc++.h>
  using namespace std;
  const int N = 6100;
  int C[4][4][4], X[N], Y[N], S, n, m, i, j, X1, x2, Y1, y2, b1, b2, b3, t;
  long long eee, eoo;
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  int S2(int x1, int y1, int x2, int y2, int x3, int y3) {
    int res = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
    res %= 4;
    if (res < 0) res += 4;
    return res;
  }
  int main() {
    for (scanf("%d", &n), i = 1; i <= n; ++i) scanf("%d%d", X + i, Y + i);
    for (i = 1; i <= n; ++i) {
      for (memset(C, 0, sizeof(C)), j = 1; j <= n; ++j)
        if (i != j)
          C[X[j] % 4][Y[j] % 4][gcd(abs(X[i] - X[j]), abs(Y[i] - Y[j])) % 4]++;
      for (X1 = 0; X1 < 4; ++X1)
        for (Y1 = 0; Y1 < 4; ++Y1)
          for (b1 = 0; b1 < 4; ++b1) {
            for (t = C[X1][Y1][b1]--, x2 = X1 & 1; x2 < 4; x2 += 2)
              for (y2 = Y1 & 1; y2 < 4; y2 += 2)
                for (b2 = b1 & 1; b2 < 4; b2 += 2) {
                  S = S2(X[i], Y[i], X1, Y1, x2, y2);
                  S >>= 1;
                  b3 = gcd(abs(X1 - x2), abs(Y1 - y2));
                  if ((S - (b1 + b2 + b3) / 2 + 1) & 1) {
                    if (b1 & 1)
                      eoo += t * C[x2][y2][b2];
                    else
                      eee += t * C[x2][y2][b2];
                  }
                }
            C[X1][Y1][b1]++;
          }
    }
    printf("%lld\n", eee / 6 + eoo / 2);
  }
  