## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Prime Factor Division CodeChef Solution

## Problem

Mario has reached Bowser's Castle and is inches away from rescuing Princess Peach. He has to answer the following problem at the gate to be allowed to enter. Can you help him?

Let $S(M)$ denote the set of all prime factors of $M$.
Given two positive integers $A$ and $B$, determine whether $A$ is divisible by all elements in $S(B)$.

### Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of a single line of input, $A$ and $B$, as mentioned in the statement.

### Output Format

For each test case, print YES if $A$ is divisible by all elements in $S(B)$ and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YESyEsyes, and yeS will all be treated as identical).

### Explanation:

Test case $1$: The set of all prime factors of $B = 63$ is given by $S(B) = \{3, 7\}$. Also, $A = 21$ is divisible by all elements in $S(B)$.

Test case $2$: The set of all prime factors of $B = 72$ is given by $S(B) = \{2, 3\}$. Also, $A = 72$ is divisible by all elements in $S(B)$.

Test case $3$: The set of all prime factors of $B = 20$ is given by $S(B) = \{2, 5\}$. Here, $A = 25$ is not divisible by $2$ in $S(B)$.