import math def get_parent(p, q): new_p = p + 1 new_q = q + 1 g = math.gcd(new_p, new_q) return (new_p // g, new_q // g) Q = int(input()) for _ in range(Q): p_u, q_u, p_v, q_v = map(int, input().split()) # Initialize current nodes for u and v current_u = (p_u, q_u) current_v = (p_v, q_v) # Check if they are the same initially if current_u == current_v: print(current_u[0], current_u[1]) continue # Use dictionaries to track visited nodes visited_u = {current_u: True} visited_v = {current_v: True} found = False while not found: # Move u up one step current_u = get_parent(*current_u) if current_u in visited_u: pass # Not necessary as each node has a unique path visited_u[current_u] = True # Check if current_u is in visited_v if current_u in visited_v: print(current_u[0], current_u[1]) found = True break # Move v up one step current_v = get_parent(*current_v) if current_v in visited_v: pass visited_v[current_v] = True # Check if current_v is in visited_u if current_v in visited_u: print(current_v[0], current_v[1]) found = True break