A sequence is beautiful if the number of times each number appears in that sequence is divisible by $5$. For example, $(1, 1, 1, 1, 1, 3, 3, 3, 3, 3)$ is beautiful while $(1, 1, 1, 1, 1, 3)$ is not.

You are given $Q$ queries, each comprises two integers $N, M$. You must count the number of beautiful sequences of $N$ integers where each element ranges from $1$ to $M$. (Two sequences are different if there exists a position where elements in two sequences are different.)

Input format

• First line: Integer $Q$ denoting the number of queries
• Each of the $Q$ following lines: Two space-separated integers $N, M$

Output format

• For each query, print the answer to the modulo $5011$ in a single line.

Constraints

$1 \le Q \le 1000$

$1 \le N \le 10^{18}$

$1 \le M \le 10^{18}$