G. LCM Subset Count
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Determine how many non-empty subsets of the numbers from $$$1$$$ to $$$n$$$ there are such that the least common multiple (LCM) of the numbers in the subset is a multiple of $$$k$$$.

Input

The first line of input will consist of a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases.

Each of the next $$$t$$$ lines will consist of two integers $$$n$$$ and $$$k$$$ $$$(1 \le n,k \le 10^{18})$$$.

It is also guaranteed that all $$$n$$$ and $$$k$$$ can be factorized with primes smaller than $$$10^6$$$.

Output

Since the output can be large, print it modulo $$$998244353$$$.

Example
Input
4
4 4
6 6
17 10
6 7
Output
8
44
114304
0