# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Fast Co-Prime

Limits: 1s, 256 MB

Two numbers **A** and **B** are called co-prime if the only common positive factor of the two numbers is **1**.

You are given two positive integers **N** and **K**, you have to find out how many numbers from **N** to **N*K** are co-prime with **N**.

### Input

The first line contains **T ( 1<=T<=100 )**, the number of testcases.

Each of the next **T** lines contain two space separated integers, **N( 2<=N<=1000000000 )** and **K( 1<=K<=1000 )**.

### Output

For each testcase, print a single line with the number of co-primes for the corresponding testcase.

### Samples

Input | Output |
---|---|

2 5 2 6 2 | 4 2 |

**6**, **7**, **8**, **9** are co-prime with **5** in the range **( 5, 10 )**.

Only **7** and **11** are co-prime with **6** in the range **( 6, 12 )**.

#### himuhasib

Hasib is passionate about sport programming and artificial intelligence. He was an IOI participant through years 2013-2015. He qualified to ACM-ICPC World Finals 2016. He studies at North South University. →