Calculate GCD

Given A,B print the number of pairs (a,b) such that GCD(a,b)=1 and 1<=a<=A and 1<=b<=B.

Input:
First line contains an integer T, the number of testcases. Each of next T lines contains two space separated integers denoting A and B.

Output:
Output T lines, each containing single integer, the required output for each test-case.

Constraints:
1 <= T <= 10
1 <= A <= 10^5
1 <= B <= 10^5

Need smart ways to find prime numbers as bruteforce is not working. Preferable in C#

You can use sieve of eratosthenes.

You can refer this link for an implementation in C# : http://rosettacode.org/wiki/Sieve_of_Eratosthenes#C.23

Please Don’t answer this as it is being used in live contest (wipro internal contest) on HackerEarth (http://www.hackerearth.com/wipro-codestorm/).

It can be answered after 02 Jun 2014, 12:30 PM.

//