I feel determined about the correctness of the code. Don't know why it shows "Wrong Answere" after testcase 3.I shall be gratefull to who explains the awesome magic involved.

public class Solution { static HashMap G=new HashMap();

public static int gcd(int x, int y){
    int z=0;
    if(x==0)z=y;
    if(G.get(x*100000+y)!=null)
    z=G.get(x*100000+y);

    if(z==0)
    z=gcd(y%x,x);
    G.put(x*100000+y,z);

    return z;

}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int q = in.nextInt();
    int[] a = new int[n];
    for(int a_i=0; a_i < n; a_i++){
        a[a_i] = in.nextInt();
    }
    int[] b = new int[m];
    for(int b_i=0; b_i < m; b_i++){
        b[b_i] = in.nextInt();
    }
    int M[][]=new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                M[i][j]=gcd(a[i],b[j]);

    for(int a0 = 0; a0 < q; a0++){
        int r1 = in.nextInt();
        int c1 = in.nextInt();
        int r2 = in.nextInt();
        int c2 = in.nextInt();
        // your code goes here
         HashSet<Integer> G1=new HashSet<Integer>();
         for(int i=r1;i<=r2;i++)
            for(int j=c1;j<=c2;j++)
                G1.add(M[i][j]);
        System.out.println(G1.size());
        G1.clear();

    }






}

}