CSPATH - Cartesian Shortest Path

The task is simple, on the 2D cartesian coordinate system, how many different shortest path from point O(0,0) to point A(x,y), but not through point B(x1,y1) and C(x2,y2).

Example Picture

Score is the length of your source.

Input

The first line is an integer T(1 ≤ T ≤ 10000), denoting the number of test cases. Then, T test cases follow.

Each test case consist of 3 lines:
-first line contains two integer x and y(1 ≤ x,y ≤ 10) location of point A
-second line contains two integer x1(0 ≤ x1 < x) and y1(1 ≤ y1 ≤ y) location of point B
-third line contains two integer x2(1 ≤ x2 ≤ x) and y2(0 ≤ y2 < y) location of point C

Output

For each test case, output number of different shortest path from (0,0) to point A but not through point B and C.

Example

Input:
2
4 5
3 4
2 2
3 3
2 1
1 2

Output:
32
2

 

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2012-06-29
Time limit:1.351s
Source limit:450B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2013-06-28 09:11:41 priyanka
If possible, could you please check submission #9564891.I've tried all test cases I could think of and can't seem to get why it's wrong.
Ans: Of course, It's overflow problem. Some of your output is negative value..

Last edit: 2013-06-29 06:17:29
2012-09-06 17:45:49 Loers
450 B this is soooooooooo unfair >.<
2012-07-13 14:45:58 Mitch Schwartz
Can we assume B and C are distinct?

Ans: sometimes B and C could be same.

Thanks for the reply.

Last edit: 2012-06-30 19:54:11
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.