PRA1: Hired! // Advanced

You've been hired by Rotato Farms Inc. to write a program that calculates the GCD between two given numbers. Easy, right? Well, apparently the last consultant the company hired had a bit of a temper, so when he was laid off and replaced by you, he smashed the computer with his baseball bat causing it to output hexadecimal numbers! Your mission, should you choose to accept it, is to take in two hexadecimal integers and return one decimal number (so the company can read it) and one hexadecimal number (so the broken computer can read it), each representing the Greatest Common Denominator of the two inputs.

Input Format

Two lines each containing a four digit hexadecimal number x, such that 0000 <= x <= ffff. Each letter in the hexadecimal number will be capital

Sample Input

047B
0965

Output Format

Two lines. The first containing a decimal number (any length) and the second number containing a four digit hexadecimal number. Any letters in the hexadecimal number must be capital.

Sample Output

37
0025