### Problem Statement

An "n-dimensional grid of size k" contains k^n cells. Each cell can be represented as an n-tuple of values from the set {0,1,...,k-1}. For example a 2-dimensional grid of size 3 is just a 3 x 3 square, with cells (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) and (2,2). A 3-dimensional grid of size 5 is a cube containing 125 cells. Cell (0,2,2) is the cell in row 0, column 2, layer 2.

Higher dimensions get a little harder to describe geometrically, but not algebraically! Every cell in an n-dimensional grid can be uniquely represented by an n-tuple specifying the "row" "column" "layer" "plane" "hyper-row" etc. (English fails us at about the same point as geometry fails us). We can define a straight line in an n-dimensional grid algebraically. It is a set of distinct cells that can be placed in a sequence such that the difference between each pair of adjacent cells is the same throughout the sequence. Of course, the difference between two n-tuples is an n-tuple. A maximal line in an n-dimensional grid of size k is a line containing k cells.

In a 3-dimensional grid of size 4, one example of a maximal straight line is (3,0,1),(2,1,1),(1,2,1),(0,3,1) which is a straight line of length 4. The difference between each pair of adjacent cells in the sequence is (-1,1,0).

You want to create a maximal line in your n-dimensional grid by adding to a collection of cells that have already been chosen. Create a class TupleLine that contains the method quickLine that takes an int size and a String[] chosen as inputs and returns the smallest number of additional cells that you could choose to form a maximal line in the grid.

Each String in chosen is a sequence of digits indicating a particular cell. For example, "410" would indicate the cell at row 4, column 1, layer 0 in a 3-dimensional grid whose size is at least 5 (since it has a row 4). The dimension of the grid is always the same as the length of each String in chosen.

### Definition

 Class: TupleLine Method: quickLine Parameters: int, String[] Returns: int Method signature: int quickLine(int size, String[] chosen) (be sure your method is public)

### Constraints

-size is between 3 and 9 inclusive
-chosen contains between 1 and 50 elements inclusive
-each character in each element of chosen is a digit whose value is less than size
-each element in chosen contains the same number of characters, n. n is the dimension of the grid and is between 2 and 9 inclusive

### Examples

0)

 `4` `{"00","02","21"}`
`Returns: 2`
 ``` X - X - X X X X - - - - - - - - - X - - - X - - - - - - - - - - ``` The left-hand picture shows the original situation. The right-hand picture shows the only way of completing a maximal line by adding two X's.
1)

 `4` `{"00","32","21","32"}`
`Returns: 3`
 ``` X - - - - - - - - X - - - - X - ``` There are lots of ways to form a maximal line with 3 more cells. Note that the cell "32" appears twice in chosen but, of course, this does not help us to form a maximal line.
2)

 `3` `{"0022","0202","0112","0000","0112"}`
`Returns: 0`
 These first three cells already form a maximal line in this 4-dimensional grid.
3)

 `9` `{"2355846","6355842","3355848"}`
`Returns: 7`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=890

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4462&pm=890

dgoodman

#### Testers:

lbackstrom , brett1479

Math, Search