Hardest Calculation Ever!!!

Author: QuwsarOhi

Problem Setter: Monzurul Islam

Intake 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
Login To Submit