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}\)