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 ≤ 10¹⁸).

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