java
import java.util.*;
import java.io.*;

/*
  --------------------------------------------------------------
  PRODUCT PATH
  --------------------------------------------------------------
  
  We are given two positive integers N and M, and we define two
  infinite arrays A and B by

     A[i] = 0  unless i divides N,
     A[i] = max(i, N/i)  if i divides N.

     B[i] = 0  unless i divides M,
     B[i] = max(i, M/i)  if i divides M.

  We then consider the 2D grid of points (x,y) with x>0, y>0.
  The "cost" of a point (x,y) is A[x]*B[y].  Notably, this is
  nonzero exactly when x divides N and y divides M.

  We want to move from (1,1) to (P,Q) by unit steps up/down/
  left/right (staying strictly in positive coordinates).  The 
  total cost of a path is the sum of the costs of all visited
  grid-points (including the start and end).

  We must find the minimum possible total cost.

  --------------------------------------------------------------
  KEY INSIGHT / PROOF SKETCH
  --------------------------------------------------------------

  1) Which points (x,y) have nonzero cost?
     Exactly those for which x|N and y|M.  Call such points
     "dangerous."

  2) Can we avoid visiting any "dangerous" points other than
     possibly (1,1) and (P,Q)?
     - Yes.  Whenever we are in a row x that divides N, we can
       choose a column y that does NOT divide M (so B[y]=0),
       hence cost=0 at (x,y).
     - Whenever we are in a column y that divides M, we can
       choose a row x that does NOT divide N (so A[x]=0),
       hence cost=0 at (x,y).
     - Because we can move around in the first quadrant without
       bounds (other than x>0,y>0), we can always “detour” 
       around any other danger‐points.  In effect, one need only
       pay for a "danger‐point" if one is forced to stand on it.

  3) Are we forced to stand on (1,1)?
     - Yes.  We start there.  Since 1 divides every positive N
       or M, (1,1) is always "dangerous" unless possibly N=1 
       or M=1, but even then A[1]*B[1] could be nonzero. 
       So the start always contributes cost = A[1]*B[1] = N*M
       (if N>1 and M>1) or N*M anyway if either is 1.

  4) Are we forced to stand on (P,Q)?
     - Yes, we finish there.  We pay A[P]*B[Q] if and only if
       P divides N and Q divides M; otherwise that cost is 0.

  5) By detouring, we can avoid all other danger‐points.  Hence
     the minimum total cost is simply:
       
       cost = A[1]*B[1]   +   [A[P]*B[Q] if (P divides N and Q divides M)]

     = (N*M)             +   [max(P, N/P)*max(Q, M/Q)  if P|N,Q|M, else 0]

  6) Edge cases:
     - If N=1 or M=1, the formula still holds:
       A[1]=N, B[1]=M => cost(1,1)=N*M.  We pay that for start.
       If (P,Q) also divides (N,M) => then (P,Q)=(1,something) 
       or (something,1).  The only subtlety is that if (P,Q)=(1,1)
       we do not double‐count it; but the problem statement 
       includes the cost of both start and end in the path cost.
       Since they are the same point, we only add it once.  But
       that is naturally handled if one thinks “sum of each
       visited point.”  So effectively the formula is consistent.

  --------------------------------------------------------------
  CONCLUSION
  --------------------------------------------------------------
  The minimal path cost is:
  
     cost(1,1)  +  cost(P,Q)  (if P,Q are dangerous),
  
  and zero otherwise in between.  Where cost(1,1)=A[1]*B[1] and
  cost(P,Q)=A[P]*B[Q].

  That is exactly N*M + (max(P, N/P)*max(Q, M/Q)) if (P divides N
  and Q divides M), and N*M alone if N,M>1, or some smaller product
  if N=1 or M=1, etc.

  We do NOT actually have to run a graph search for large N,M.
  A direct check of divisibility suffices.

*/


class Codechef
{
    // Reads divisors of n in O(sqrt(n)) time.
    // Not actually needed for the final formula, but shown for reference.
    static ArrayList<Long> divisors(long n) {
        ArrayList<Long> divs = new ArrayList<>();
        for(long i=1; i*i<=n; i++){
            if(n%i==0){
                divs.add(i);
                if(i*i!=n) divs.add(n/i);
            }
        }
        return divs;
    }

    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader();

        int T = in.nextInt();
        while(T-- > 0){
            long N = in.nextLong();
            long M = in.nextLong();
            long P = in.nextLong();
            long Q = in.nextLong();

            // cost(1,1) = A[1]*B[1]:
            //   A[1] = max(1, N/1) = N   (since N>=1)
            //   B[1] = max(1, M/1) = M   (since M>=1)
            // so cost(1,1) = N*M.
            // However, if N=1 and M=1, that is 1*1=1.

            long startCost = N * M;  // cost(1,1).

            // Does P,Q lie in the "danger set"?  That is, do P|N and Q|M ?
            // If yes, cost(P,Q) = A[P]*B[Q] = max(P, N/P)*max(Q, M/Q).
            // If not, cost(P,Q) = 0.

            long endCost = 0;
            boolean pDividesN = (N % P == 0);
            boolean qDividesM = (M % Q == 0);
            if(pDividesN && qDividesM) {
                // A[P] = max(P, N/P)
                // B[Q] = max(Q, M/Q)
                long AP = Math.max(P, N/P);
                long BQ = Math.max(Q, M/Q);
                endCost = AP * BQ;
            }

            // Special case: If (P,Q) == (1,1), we must not double-count 
            // the same cell.  The problem states "the sum of costs of 
            // all points visited (including start and end)".  If start 
            // == end, we only visit that one cell once.  So the cost 
            // is just cost(1,1).  Let's handle that:
            if(P == 1 && Q == 1) {
                // We never move anywhere.  So the total cost is just cost(1,1).
                System.out.println(startCost);
                continue;
            }

            // Otherwise, the minimal path cost is exactly:
            //   startCost + endCost
            //
            // Because we can detour around all other danger-points.
            // (Start cost is always paid, because (1,1) is always in danger-set
            //  for any N>=1,M>=1.  The final cost is paid only if (P,Q) is in
            //  danger-set.  Everything else can be avoided.)
            long ans = startCost + endCost;
            System.out.println(ans);
        }
    }

    // A faster input reader to handle up to 1000 testcases and large numbers.
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null || !st.hasMoreTokens()){
                try{ st = new StringTokenizer(br.readLine()); }
                catch(IOException e){throw new RuntimeException(e);}
            }
            return st.nextToken();
        }
        int nextInt(){ return Integer.parseInt(next()); }
        long nextLong(){ return Long.parseLong(next()); }
    }
}

Explanation of the Core Formula:

1. The only grid‐cells (x,y) that cost anything are those where x divides N and y divides M.
2. We always start at (1,1), which is indeed in that “danger” set, so we must pay cost(1,1) = A[1]·B[1] = N·M.
3. From there, provided N>1 and M>1, one can “detour” in the plane (since we can move up/down/right/left in any positive coordinate) so as to avoid ever again landing on another dangerous cell—except possibly the endpoint (P,Q).
4. Therefore the only additional cost we might be forced to pay is that of the endpoint (P,Q), namely A[P]·B[Q], but only if P divides N and Q divides M. In that case, A[P] = max(P, N/P) and B[Q] = max(Q, M/Q).

Hence the minimum total is simply:
cost(1,1) + ( cost(P,Q) if (P divides N and Q divides M) else 0 ).

With one small caveat: if (P,Q) = (1,1), we do not double‐count the same cell. In that case, the path is of length zero and the total cost is just the cost of that single cell (1,1).