CANPR - Candy pair


 

A candyseller is selling N candies.Each candy is labelled with some unique 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.

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.

hide comments
n_o_o_b_i_e: 2018-06-14 08:32:17

TLE uisng brute force


Added by:arjun8115
Date:2018-05-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own