Problem Description

When Rikka was a little girl, she met a hard but interesting problem "A good task to defend AK." This problem uses some properties about XOR $\oplus$ (exclusive OR).

Time flies, six years have passed. Rikka has become a college student. And today, Rikka recollects this task and she finds herself know little about XOR. So she wants to come up with some tasks about XOR and try to solve them.

Most of the tasks are very simple, except one of them. Soon, Rikka finds it is too difficult for her. So she asks you to give her some help. Here is the task:

Given two integers $n,m$, and she wants to calculate $\prod_{i=0}^m n \oplus i$. The answer may be very large, she just wants to know the answer modulo $1500000001$.

Input

The first line contains one single integer $t(1 \leq t \leq 20)$, the number of the testcases.

For each testcase, the first line contains two integers $n,m(1 \leq m < n \leq 10^9)$.

Output

For each testcase, output a single integer, the answer modulo $1500000001$ which is a prime number.

3
3 2
7 5
654321 123456

6
5040
1230647278