# Practice on Toph

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

Toph is experiencing some technical difficulties. We are sorry for the inconvenience.

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

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.

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

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

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

2 5 2 6 2 | 4 2 |

For the first input, 6, 7, 8, 9 are co-prime with 5 in the range (5, 10). For the second input, only 7 and 11 are co-prime with 6 in the range (6, 12). |

61% Solution Ratio

Sherlock221bEarliest,

prodip_bsmrstuFastest, 0.0s

riadroxLightest, 0 B

user.055255Shortest, 336B

Login to submit

NSU Code Masters 2016 Ended |

Replay of NSU Code Masters 2016 Ended |