For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Painting Square

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasily 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.

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

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

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.

Input

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.

Output

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.

Examples

Input

8

1 0

1 1

3 0

3 1

2 0

2 1

3 2

7 2

Output

1

0

1

1

1

0

0

4

Note

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2017 23:46:28 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|