1548_D2. Gregor and the Odd Cows (Hard)_6
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>
import java.io.*;
import java.util.*;
 
public class solution {
    static FastScanner sc;
    static PrintWriter pw;
    
    static long[][] gcds;
    static final int D = 2000;
 
    public static void main(String[] args) {
        sc = new FastScanner();
        pw = new PrintWriter(System.out);
 
        int N = sc.ni();
        
        //precompute small GCDs
        gcds = new long[D][D];
        for (int i = 0; i < D; i++) {
            for (int j = 0; j <= i; j++)
                gcds[i][j] = calcGCD(i,j);
        }
 
        long[][] nums = new long[N][2];
        int[][] mods = new int[N][2];
        for (int i = 0; i < N; i++) {
            nums[i] = new long[]{sc.nl(),sc.nl()};
            mods[i][0] = (int)nums[i][0]%4;
            mods[i][1] = (int)nums[i][1]%4;
        }
 
        int[][][][] cnt = new int[N][4][4][4]; //number of other points with modularity (j,k) such that the segment from i has modularity l boundary points.
        for (int i = 0; i < N; i++) {
            for (int other = i+1; other < N; other++) {
                int b = boundary(nums[i][0],nums[i][1],nums[other][0],nums[other][1]);
                cnt[i][mods[other][0]][mods[other][1]][b] += 1;
                cnt[other][mods[i][0]][mods[i][1]][b] += 1;
            }
        }
 
        //a little manipulation by pick's theorem: a fence is interesting IFF A (2*area) is congruent to B (total boundary points) modulo 4.
        //since A is even, b1,b2,b3 (where B=b1+b2+b3) are either all even or one is even.
 
        long eee = 0;
        long ooe = 0;
 
        //fix one vertex
        for (int i = 0; i < N; i++) {
            //fix the modularities of b1 and b2
            for (int b1 = 0; b1 < 4; b1++) {
                for (int b2 = b1; b2 < 4; b2 += 2) {
                    //fix the modularities of the other points
                    for (int x1 = 0; x1 < 4; x1++) {
                        for (int y1 = 0; y1 < 4; y1++) {
                            int startx2 = b1<b2 ? x1%2 : x1;
                            for (int x2 = startx2; x2 < 4; x2 += 2) {
                                int starty2 = x1!=x2||b1<b2 ? y1%2 : y1;
                                for (int y2 = starty2; y2 < 4; y2 += 2) {
                                    int b3;
                                    int triangles;
                                    if (x1==x2 && y1==y2) {
                                        b3 = 0;
                                        if (b1==b2)
                                            triangles = cnt[i][x1][y1][b1]*(cnt[i][x1][y1][b2]-1)/2;
                                        else
                                            triangles = cnt[i][x1][y1][b1]*cnt[i][x1][y1][b2];
                                    } else {
                                        b3 = 2;
                                        triangles = cnt[i][x1][y1][b1]*cnt[i][x2][y2][b2];
                                    }
                                    int B = (b1+b2+b3)%4;
                                    if (area(nums[i][0],nums[i][1],x1,y1,x2,y2) == B) {
                                        if (b1%2==0&&b2%2==0)
                                            eee += triangles;
                                        else
                                            ooe += triangles;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        long ans = eee/3+ooe;
        pw.println(ans);
 
        pw.close(); 
    }
 
    //shoelace formula for A (2*area)
    public static int area(long x1, long y1, long x2, long y2, long x3, long y3) {
        return (int)(Math.abs(x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3)&3);
    }
 
    //number of boundary points between two points
    public static int boundary(long x1, long y1, long x2, long y2) {
        return (int)(gcd(Math.abs(x1-x2),Math.abs(y1-y2))&3);
    }
 
    public static long calcGCD(long a, long b) {
        if (a < b)
          return gcd(b,a);
        if (b == 0)
          return a;
        else
          return gcd(b,a%b);
    }
    
    public static long gcd(long a, long b) {
        if (a < b)
          return gcd(b,a);
        if (a < D)
            return gcds[(int)a][(int)b];
        else if (b == 0)
          return a;
        else
          return gcd(b,a%b);
    }
	
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in), 32768);
            st = null;
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int ni() {
            return Integer.parseInt(next());
        }
 
        long nl() {
            return Long.parseLong(next());
        }
    }
}