public static long gcd(long p, long q){
        if (q==0) return p;
        long r = p % q;
        return Math.abs(gcd(q, r));
    }