Hardest Calculation Ever!!!
Author: QuwsarOhi
Problem Setter: Monzurul IslamIntake 35, Department of CSE.
GCD stands for
Greatest Common Divisor and LCM stands for Lowest Common Multiple. You are
given an equation GCD(X, Y) + LCM(X,
Y) = X+Y where X and Y are two integers. Now your task is to
check the equation is valid or invalid
Input Format
The first line contains one integer T
(1 ≤ T ≤ 10^6), denoting the number of test cases.
Then T lines follow, each describing a
test case. Each line contains two integers X and Y (0 < X, Y ≤ 1018).
Output Format
For each test
case, if the equation is satisfied, print "Valid" and then print the
value of GCD(X, Y) + LCM(X, Y) in
the next line. If the equation is not satisfied print “Invalid”.
Samples
Input
3
5 7
10 20
2 3
Output
Invalid
Valid
30
Invalid
Limits
Language | Time | Memory |
GNU C 11 | 1s | 512MB |
GNU C++ 14 | 1s | 512MB |
GNU C++ 11 | 1s | 512MB |
Statistics