triples II
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed.
He has decided to input  multiples of 3 and the output of the program should be his favorite number .
He wants to know how many possible sequences are there. Because the answer can be large, you only need to output the answer modulo .

输入描述:

There're multiple test cases in a test file.
The first line contains a positive integer  - the number of test cases.
In each of the following  lines there're two non-negative integers  and .

输出描述:

For each test case output a line - the number of such sequences modulo .
示例1

输入

复制 
3
3 3
2 7
233 333

输出

复制 
7
2
650745136

备注:

，，。