Sheldon and the Number Hangman

locked

Sheldon and his friend Alric are playing number hangman. Sheldon is a palindrome loving person and is making a hangman game which contains number palindromes in subparts of the answer. Sheldon now needs to create an array of size N where each element can be from 1 to M. He also wants Q subarrays of this array to be palindromes. You are given the left and right index of these Q subarrays (1-based indexing). You need to help Sheldon find out the number of arrays that he can make.

Input Format

The first line of input consists of T denoting the number of testcases. For each testcase the first line contains 3 numbers N, Q, M. The next Q lines contain two integers each A, B denoting the left and right index of subarray that needs to be palindrom (1-based indexing).

Constraints

1 ≤ T ≤10
1 ≤ N ≤ 104
1 ≤ Q ≤ 100
1 ≤ M ≤ 109
1 ≤ A ≤ B ≤ N

Output Format

Print T lines, each will have number of arrays that Sheldon can create

Sample Input 0

2
3 2 1
1 2
2 3
4 1 2
1 4

Sample Output 0

1
4
Loading Editor...
  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