Description

Miruka: 1, 33, 276, 1300…?

Input

The first line of the input will be an integer T (1<=T<=10000), denoting the number of test cases.
The only line of each input will be two integers N (1 <=N<=10^8) and M (1<=M<=10^8).

Output

One line per test case, an integer equals to (Σ_k=1~N k⁵) modulo M.

Sample Input  Download

Sample Output  Download

Tags

Discuss