Lindsay and Yoda are classmates at college. Lindsay has always had a deep affection for Yoda. But after months of squiring, Yoda still had not fallen for Lindsay, not even the slightest bit. In an incident Lindsay broke into tears and asked her best male friend, Sayid, "Why? Why is Yoda so cold to me?"
"Maybe, he's just not that into you", said Sayid, who continued mysteriously, "And you know why? it's because your names do not match."
It was said that, the "into"-ness of a person for another is decided by how closely merged can their name be. Namely, "Lindsay" and "Yoda" does not match, since the shortest string they could be fused into is "lindsayoda". On the other hand, "Linsay" and "Sayid" are excellent match, as they can fuse into "lindsayid", which is shorter. Maybe that's why her friend Sayid mentioned this non-sense anyway.
More formally, given two strings A and B, the "into-ness" of string A and B is the length of the shortest possible string S, such that A is the prefix of S, and B is the suffix of S. Furthermore, S must not be exactly A or B. You want to be a matchmaker when you grow up, and you decide to practice your programming skill which may come in handy. (how?) Therefore, you are given a pool of names (strings of length <= 128) S1, S2, ... Sn, you are to find for all i != j, the "into-ness" of string Si and Sj.
The first line contain an integer T --- the number of tests(1<=T<=15).
Each test begins with one line only contains one integer n(0<=N<=1000), denoting the number of names. Then following n lines, i-th line contains one string Si.
For each tests, you have to print n lines contain a n*n matrix. The main diagonal of this matrix have to be filled zero. And you have to fill the length of the minimum string that Si is the prefix of it and Sj is the suffix of it, and it's either Si or Sj, in i-row j-column (i ≠ j) of the matrix.
1 3 ababc abcab cabca
0 7 9 8 0 7 9 6 0
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|