You are given two numbers n and k. For each number in the interval [1, n], your task is to calculate its largest divisor that is not divisible by k. Print the sum of these divisors.

Note: k is a prime number.

Input format

• The first line contains an integer T representing the number of test cases that will follow.
• Each test case consists of one line containing two integers n and k.

Output format

The output must contain the answer for each test case on a different line.

Each answer consists of a single integer.

Constraints

\(T \le 300000\\ 1 \le n \le 1000000000\\ 2 \le k \le 1000000000\)