Eldor is student and he likes to work with big numbers. He is learning to find GCD (Greatest Common Divisor) of two big numbers.

Now he has N pairs of big numbers. He wants to find sum all of pairs of GCD. Please, help to Eldor  for to solve this problem.

Input:

Given the first line single integer number N (1<=N<=1000) – number of X and Y pairs. The next N lines given X and Y number of pairs(1<=X,Y<=10¹⁰⁰).

Output:

Your task to print single integer number – the answer this problem.