## PGCD - Primes in GCD Table

Johnny has created a table which encodes the results of some operation -- a function of two arguments. But instead of a boring multiplication table of the sort you learn by heart at prep-school, he has created a GCD (greatest common divisor) table! So he now has a table (of height `a` and width `b`), indexed from (1,1) to (`a`,`b`), and with the value of field (`i`,`j`) equal to gcd(`i`,`j`). He wants to know how many times he has used prime numbers when writing the table.

### Input

First, `t` ≤ 10, the number of test cases. Each test case consists of two integers, 1 ≤ `a`,`b` < 10^{7}.

### Output

For each test case write one number - the number of prime numbers Johnny wrote in that test case.

### Example

Input:2 10 10 100 100Output:30 2791

hide comments

Przemys³aw Uznañski:
2011-11-20 02:19:14
Oh, it's nice to find my problem from codechef ported to spoj. Cheers :) |

Added by: | Yash |

Date: | 2009-06-12 |

Time limit: | 0.687s |

Source limit: | 11111B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | Codechef |