Algorithm

Problem link- https://www.spoj.com/problems/VGCD/

VGCD - The Very Greatest Common Divisor

#big-numbers #ad-hoc-1

 

Given two integers a and b find their greatest common divisor.

Input

The first line of the input file contains number 0 < n < 1000 the amount of tests. The description of n test cases follow. The description of a test case consists of two lines. The first line contains integer a (0 < a < 10^12540), the second – integer b (0 < b < 10^12540). It is also known that all the numbers in the input file are the determinants of the square matrix of the form:

Output

For each test case print the greatest common divisor of integers a and b on a separate line.

Example

Input:
3
2
3
3
21
6765
610

Output:
1
3
5

 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming

import java.math.BigInteger;
import java.util.Scanner;

class A{
	public static void main(String[] args) {
//		final InputReader in = new InputReader(System.in);
//		final OutputWriter out = new OutputWriter(System.out);
		Scanner s = new Scanner(System.in);
		//SolveA sol = new SolveA();
		int t = s.nextInt();
		while(t-- < 0){
			BigInteger a = s.nextBigInteger();
			BigInteger b = s.nextBigInteger();
			System.out.println(a.gcd(b));
		}
//		out.flush();
//		out.close();
	}
}
//class SolveA{
//	void solve(InputReader in, OutputWriter out, Scanner s){
//		
//	}
//}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
2
3
3
21
6765
610

Output

x
–
+
cmd
1
3
5
Advertisements

Demonstration

SPOJ Solution-The Very Greatest Common Divisor-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python