[Solution] To Divide or Not To Divide solution codechef

To Divide or Not To Divide solution codechef – Alice likes all the numbers which are divisible by A. Bob does not like the numbers which are divisible by B and likes all the remaining numbers. Determine the smallest number greater than or equal to N which is liked by both Alice and Bob. Output -1 if no such number exists.

Table of Contents

[Solution] To Divide or Not To Divide solution codechef

  • The first line contains a single integer T — the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains three space-separated integers AB and N — the parameters mentioned in the problem statment.

Output Format

For each test case, output the smallest number \ge N which is divisible by A and is not divisible by B. Output -1 if no such number exists.

Constraints

  • 1 \leq T \leq 1000
  • 1 \leq A, B, N \leq 10^9

[Solution] To Divide or Not To Divide solution codechef

Input

Output

3
5 2 11
4 3 24
7 7 100
15
28
-1

Explanation:

Test case 1: 15 is the smallest number \ge 11 which is divisible by 5 and is not divisible by 2.

Test case 2: 28 is the smallest number \ge 24 which is divisible by 4 and is not divisible by 3.

Test case 3: There does not exist any number which is divisible by A = 7 and is not divisible by B = 7.

For Solution

Click Here

Leave a Comment