Submissions will no longer be placed on the leaderboard. You may still attempt this problem for practice.

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 .

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score