A candyseller is selling N candies.Each candy is labelled with a positive integer ai from 1 to N.

He is a little orthodox and considers some positive integer L as his Lucky number.Apart from that, he sells candies 

only in pairs.He would sell two candies ai and aj only if the greatest number which divides both ai 

and aj is his lovely number L.

To promote his candy bussiness, he has come up with an offer to customers.He would give some candies for

free to the first customer who can exactly tell the total possible number of ways W in which candy seller

can sell one pair of candies among the N available.The customer is required to adhere to his selling policy

as mentioned above.

We want you to grab the opportunity to win the free candies by telling the number of ways W.

Input

First line of input contains a positive integer T(1<=T<=100000) i.e. the number of test cases to follow.

Then T lines follow, containing two positive integers N (1<=N<=1000000) and L(1<=L<=1000000) i.e. number of candies and lucky number respectively

for each test case.

Output

For every test case,output a single non-negative integer W.

Note: Pairs (x,y) and (y,x) are considered different and both will contribute to W.

Example

Input:
2
5 1
3 2
Output:
19
1

Testcase 2: (2,2) is the only possible pair.