# Problem Definition

Frank explained its friend Felman the algorithm of Euclides to calculate the GCD of two numbers. Then Felman implements it algorithm

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

and it proposes to Frank that makes it but with a little integer and another integer that has up to 250 digits.

Your task is to help Frank programming an efficient code for the challenge of Felman.

**Input**

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 ( and ).

**Output**

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

**More on this problem is available here.**

# Solution

*Greatest common divisor* is the largest number that divides both number without any reminder. Thus, GCD is also called *Highest Common Divisor *(HCF), or *Greatest Common Factor *(GCF).

The main trick used in the solution lies in the `mod'`

function, which effectively reduces the range of the numbers to , that is:

where is the outcome of `mod'`

function .

Afterwards, a normal `gcd`

function can simply be applied on to compute the result.

//Problem Statement : https://www.spoj.com/problems/GCD2/ | |

open System | |

let parseLine() = | |

let line = System.Console.ReadLine().Split() | |

line.[0] |> int, line.[1] |> string | |

let rec gcd a b = | |

match b with | |

| 0 -> a | |

| _ -> gcd b (a%b) | |

// computes b%a | |

let mod' (b:string) (a:int)= | |

b.ToCharArray() | |

|> Array.fold (fun acc x -> ((acc*10 + (((int)x)-48))%a)) 0 | |

let rec solveLines currentLine maxLines = | |

if currentLine < maxLines then | |

let num1,num2 = parseLine() | |

match num1,num2 with | |

| 0,_ -> printfn "%s" num2 | |

| _ -> | |

mod' num2 num1 | |

|> gcd num1 | |

|> printfn "%d" | |

solveLines (currentLine+1) maxLines | |

let solveSpoj2906() = | |

match Console.ReadLine() |> Int32.TryParse with | |

| (true, i) when i > 0 -> solveLines 0 i | |

| _ -> () | |

solveSpoj2906() |