# CPP Program Advanced GCD – Number Theory

Varun explained its friend Sanchit the algorithm of Euclides to calculate the GCD of two numbers. Then Sanchit implements the algorithm

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

and challenges to Varun to calculate the gcd of two integers, one is a little integer and other integer has 250 digits.
Your task is to help Varun an efficient code for the challenge of Sanchit.

Input format:

• The first line of the input file contains a number representing the number of lines to follow.
• Each line consists of two number A and B (0 <= A <= 40000 and A <= B < 10^250).

Output format:

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

Constraints:

1 <= n <= 1000

Sample Input:

```2
2 6
10 11```

Sample Output:

```2
1```

## Code:

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```#include<iostream>
#include<string>
using namespace std;
int gcd(int a, int b)
{
if(b>a)
{
return gcd(b, a);
}
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int main()
{
int t;
cin >> t;
while (t--)
{
int a;
string b;
cin >> a >> b;
if(a==0)
{
cout<<b<<endl;
continue;
}
int current_number = 0;
for (int i = 0; i < b.size(); i++)
{
current_number = ((current_number * 10) % a + (b[i] - '0') % a) % a;
}
cout << gcd(a, current_number) << endl;
}
}
```Code language: C++ (cpp)```