## GRIDSUM1 - 2x2 Subgrid Sum Problem (medium)

no tags

This problem is a higher constraints version of KWACIK (Polish).

You are given a 3x3 grid. You can place an integer m (a ≤ m ≤ b) in each cell.

How many ways are there to place integers in the cells such that the sum of each 2x2 subgrid is n ?

### Input

The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases.

On each of the next T lines, you are given three integers a, b and n. (0 ≤ ab ≤ 500, 0 ≤ n ≤ 2000)

### Output

For each test case, output a single line containing the number of ways to place integers.

Input:

```1
1 2 5
```

Output:

`8`

### Explanation

There are 8 ways to place integers for a=1, b=2 and n=5.

```2 1 2 : 2 1 2 : 2 1 1 : 1 2 1 : 1 2 1 : 1 1 2 : 1 1 1 : 1 1 1
1 1 1 : 1 1 1 : 1 1 2 : 1 1 1 : 1 1 1 : 2 1 1 : 2 1 2 : 1 2 1
2 1 2 : 1 2 1 : 2 1 1 : 2 1 2 : 1 2 1 : 1 1 2 : 1 1 1 : 1 1 1```

### Information

- There are 7 input files.

- Changed the time limit of the input file #7 to 20 seconds and rejudged all submissions. (2014-10-17)

### Credit & Special thanks

 Added by: Min_25 Date: 2014-10-17 Time limit: 10s-20s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: KWACIK