Given two integers N and P you need to find the sum of all positive integers less than or equal to N which have no divisor smaller than or equal to P apart from 1.

Input

The first line contains one integer T - denoting the number of test cases.

T lines follow each containing two space separated integers N and P.

Output

For each test case output the required sum in a new line.

Constraints

T <= 10

2 <= P <= N <= 2,000,000,000

example

Input:
4
11 7
10 10
4 2
7 2

Output:
11
0
3
15