Recursive GCD

Lab C Beginner 10 points

Write int gcd(int a, int b) recursively (gcd(a, 0) = a). Print the GCD of each pair.

Input

n, then n lines a b.

Output

n lines.

Example

Input

Output

6
1
25

Sample input available Sample output available

Editor

Hints

The recursive form of Euclid's algorithm is one line.

Solution explanation

Some algorithms are naturally recursive and read almost like their maths definition.

Show solution

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int n, a, b;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}

Output

Answer