Coloring in Hypercube

All submissions for this problem are available.

In an N-dimensional grid the co-ordinates of a cell are denoted as X₁, X₂, ..., X_N. Any cell with negative co-ordinate are colored white. The origin cell (the one with all zero co-ordinates) is colored as black. The color of a cell in (X₁, X₂, ..., X_N) depends on the N cells with co-ordinates (X₁-1, X₂, ..., X_N), (X₁, X₂-1, ..., X_N), ...., (X₁, X₂, ..., X_N-1). The cell is colored white if and only if the number of black colored cells among these N co-ordinates are even, otherwise the cell is colored black.

You are given the starting and ending co-ordinate of sub-hypercube. You need to compute how many hyper cells in this sub hypercube are colored black.

Input

First line of the input contains T the number of test cases. Each test case starts with a line containing N the dimension of the hypercube. The second line contains N integers denoting the co-ordinate of the starting cell of the hypercube. The third line contains N integers denoting the co-ordinate of the ending cell of the hypercube.

Output

For each test case, output the number of black colored cells in the given hypercube. Since the result can be too big so output the result modulo 1000000009.

Example

Input

3
3
4 0 4
7 9 8
2
0 3
10 9
4
0 3 0 2
6 8 1 5

Output:

9
32
22

Constraints

T < 51
0 < N < 9

All the co-ordinates will be non negative integers with at most 15 digits.

---

Date:	2011-06-06
Time limit:	4s
Source limit:	50000B
Languages:	All