瓦西里熊有一张 n 行 n 列的白色方形大桌子。桌子周围有黑色边框。
n = 5 时的初始表示例。
瓦西里熊想用 k 步画出他的方桌。每个动作都是一系列动作:
1. 小熊选择桌子内的某个方格。此时正方形周围必须画有黑色边框。此外,正方形不应包含黑色单元格。正方形中的单元格数量不应少于 2 个。
2. 小熊在所选方格内选择一些行和一些列。然后他在所选正方形内绘制该行和该列的每个单元格。之后,由正方形边框和新绘制的单元格形成的矩形必须是非零面积的正方形。
n = 7 и k = 2 时正确绘画的示例。
熊已经知道数字 n 和 k。帮助他 — 找出在 k 步内绘制正方形的方法数。如果生成的表格至少在一个单元格中不同,则两种绘制方式称为不同的绘制方式。由于答案可能相当大,因此打印除以 7340033 后的余数。
输入
第一行包含整数 q (1 ≤ q ≤ 105) — 测试数据的数量。
以下 q 行中的每一行包含两个整数 n 和 k (1 ≤ n ≤ 109, 0 ≤ k ≤ 1000) — 初始表的大小和相应测试的移动次数。
输出
对于输入中的每个测试,打印问题的答案以 7340033 为模。按照输入中给出测试的顺序打印测试的答案。
示例
输入 #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
注意
测试 n = 7 和 k = 2 的所有可能的绘画方式是: