D. Покраска квадрата
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У медведя Василия есть большая квадратная таблица белого цвета, составленная из 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. Ответы для тестов выводите в том порядке, в котором тесты заданы во входных данных.

Примеры
Входные данные
8
1 0
1 1
3 0
3 1
2 0
2 1
3 2
7 2
Выходные данные
1
0
1
1
1
0
0
4
Примечание

Все возможные покраски для теста n = 7 и k = 2: