A candy seller 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 business, 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

Test case 2: (2, 2) is the only possible pair.