## LONGCS - Longest Common Substring

Substrings are consecutive parts of a string. A problem usually solved with dynamic programming is to find the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two strings.

Your task is to find the length of the longest common substring of K strings.

### Input

The first line contains an integer T, the number of test cases (1 ≤ T ≤ 20) . Each test case, consists of one line containing an integer K (1 ≤ K ≤ 10), and K lines, each containing a string (length of s <= 10^4), the strings only contain the character ‘a’ – ‘z’.

### Output

Output T lines, one for each test case, containing the required sequence, with a blank space between consecutive terms. It is guaranteed that all terms in the sequence are integers.

### Example

Input:2 2 aaabbb bbaabb 3 icode coder contestOutput:4 2

hide comments

qamichaelpeng:
2020-12-08 07:10:01
for suffix array solution, quick sort will tle, bucket sort works. |

Added by: | Paulo Costa |

Date: | 2012-02-07 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | UNI |