CF300D.Painting Square

Vasily the bear has got a large square white table of n rows and n columns. The table has got a black border around this table.

The example of the initial table at n = 5.

Vasily the bear wants to paint his square table in exactly k moves. Each move is sequence of actions:

1. The bear chooses some square inside his table. At that the square must have a black border painted around it. Also, the square shouldn't contain a black cell. The number of cells in the square shouldn't be less than 2.
2. The bear chooses some row and some column inside the chosen square. Then he paints each cell of this row and this column inside the chosen square. After that the rectangles, formed by the square's border and the newly painted cells, must be squares of a non-zero area.

An example of correct painting at n = 7 и k = 2.

The bear already knows numbers n and k. Help him — find the number of ways to paint the square in exactly k moves. Two ways to paint are called distinct if the resulting tables will differ in at least one cell. As the answer can be rather large, print the remainder after dividing it by 7340033.

瓦西里熊有一张大小为 $n$ 行 $n$ 列的大型白色方格表。该表格四周有一圈黑色边框。

初始表格的一个示例（当 $n = 5$ 时）。

瓦西里熊希望恰好用 $k$ 步将这张方形表格涂满颜色。每一步包含如下一系列操作：

1. 熊在表格内部选择一个正方形区域，该正方形区域必须已被黑色边框包围，且其内部不能含有任何黑色格子；此外，该正方形所含的格子数不得少于 2。
2. 熊在所选正方形区域内选择某一行和某一列，然后将该行与该列在该正方形区域内的所有格子全部涂黑。涂黑后，由该正方形的原始边框与新涂黑的行、列所形成的各个矩形，必须均为面积非零的正方形。

当 $n = 7$ 且 $k = 2$ 时的一个合法涂色示例。

熊已知 $n$ 和 $k$ 的值。请你帮助他——求出恰好用 $k$ 步完成涂色的方案总数。若两种涂色方案最终得到的表格在至少一个格子上颜色不同，则称它们是不同的方案。由于答案可能非常大，请输出其对 $7340033$ 取模的结果。

The first line contains integer q (1 ≤ q ≤ 105) — the number of test data.

Each of the following q lines contains two integers n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ 1000) — the size of the initial table and the number of moves for the corresponding test.

第一行包含一个整数 $q$（$1 \le q \le 10^5$）——测试数据的组数。

接下来的 $q$ 行，每行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^9$，$0 \le k \le 1000$）——分别表示对应测试用例中初始表格的大小以及移动次数。

For each test from the input print the answer to the problem modulo 7340033. Print the answers to the tests in the order in which the tests are given in the input.

对输入中的每个测试用例，输出该问题的答案对 7340033 取模的结果。按照输入中测试用例给出的顺序输出各测试用例的答案。

All possible painting ways for the test n = 7 and k = 2 are:

测试用例 $n = 7$ 和 $k = 2$ 的所有可能涂色方案为：