Module: (Python) Practicum 4. Euclid's Algorithm


Problem

6 /6


Task for Petya and Vanya

Problem

Fifth graders Petya and Vanya learned the following Euclid algorithm in math class:

  1. Let a, b — the numbers to be found.

  2. If b = 0 then number a — GCD you are looking for.

  3. If b > a then swap the numbers a and b .

  4. Set a a value a – b.

  5. Return to step 2.

Masha came up with a task for them to fix. She asked the boys to come up with such numbers a, b, c and d that in the process of implementing the Euclid algorithm for a given pair of numbers (a, b) , there comes a moment when, before step 2 is executed, the number a will be equal to c , and the number b will be equal to d.

Write a program for Masha to check if the numbers satisfy a, b, c, d Masha's conditions.

Input: The first line of the input contains the number of test cases K (\( 1 <= K <= 100\)). Below are descriptions of these sets. Each description consists of two lines. The first one contains two integers: a, b (\(1 <= a, \ b <= 10^{18}\)). The second line – two integers: c, d (\(1 <= c,\ d < = 10^{18}\)).
All numbers in the lines are separated by spaces.

Output: For each test case, output the word «YES» if during application Euclid's algorithm to a pair of numbers (a, b) at some point a pair is obtained (c, d< /code>). Otherwise, output the word "NO".

 

Examples
# Input Output
1 2
20 10
10 10
10 7
24		 YES
NO

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!