We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Combinatorics
  4. Highway Construction

Highway Construction

You are planning the next FIFA World Cup and you are counting the number of highways that need to be built to connect the cities with the venue.
Your country has cities and all cities lie on a single straight road called “Highway Road”. If you want to go from City to City ( where ), you need to go through city .

The requirements for the highways are as follows:

  1. All games will be held in the city.
  2. New bidirectional roads, called "Super Highways", need to be built such that it is possible to visit the city from any other city directly.

You also have the cost to fulfil the second condition. The engineering team knows that if the length of a Super Highway is , then it will cost , where is an integer constant.The length of Super Highway between city and is .

For this problem, you need to find only a rough estimation of the cost, hence, find Total Cost Modulo .

Input Format

First line will contain a single positive integer denoting the number of queries. Then for each case there will be two positive integers, and .

Constraints

Output Format

For each case find the cost to build Super Highways such that it is possible to visit city from any other city directly. You have to print this value Modulo .

Sample Input 0

1
4 2

Sample Output 0

13

Explanation 0

There are four cities. We need to build Super Highways that connect city to city and city to city . No need to connect city 3 with city since they are adjacent on “Highway Road”. So cost is .