Painting Square

题意翻译

有人送了Vasily一张$n\times n$的白色表格，外围包了一圈黑色边框。如图1，是一个$5\times 5$的表格。 Vasily想用$k$次操作给表格涂色，每次操作的步骤是： 1. 选择一个有黑色边框的白色子正方形。 2. 在选择的正方形里涂黑一行一列使得涂上颜色的一行一列与原正方形的边界所围成的新的矩形均为正方形且面积不为$0$。 求Vasily涂$k$次后可以得到多少不同的结果，两个结果不同当且仅当最后得到的表格中有任一格子颜色不同。 结果对$7340033$取模。

题目描述

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 $ .

输入输出格式

输入格式

The first line contains integer $ q $ $ (1<=q<=10^{5}) $ — the number of test data. Each of the following $ q $ lines contains two integers $ n $ and $ k $ $ (1<=n<=10^{9},0<=k<=1000) $ — the size of the initial table and the number of moves for the corresponding test.

输出格式

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.

输入输出样例

输入样例 #1

8
1 0
1 1
3 0
3 1
2 0
2 1
3 2
7 2

输出样例 #1

1
0
1
1
1
0
0
4

说明

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