MIB - Spelling Lists


J, of the Men In Black,  has been learning an alien language and has has a spelling test tomorrow.  J, however, is bored of studying the nonsensical (and often unpronouncable) words.

Instead, he is seeing how many ways he can reorder his spelling list.  After making all possible permutations of word on his list, he sorts the rearranged lists lexiographically (by the first word, then the second...).  After the sort, in what position, with  the lexiographically first list being in position 1, is his original spelling list?

Input

The first line is the number of spelling lists (no more than 10).

For each spelling list, a line with the number of words (no more than 1000) is given, followed by the original list on the next line.

All words within a spelling list are unique.  Each word is composed of the letters a-z, is fewer than 100 characters, and is followed by a single space.

Output

On separate lines, give the positions of the original lists.

Example

Input:
4
4
a b c d
4
d c b a
1
mrsmith
6
a aaaaaa aaaaa aaaa b bb

Output:
1
24
1
55

hide comments
lowgradde: 2024-11-05 11:25:31

You can map the input to lexicographical indices and then use recursion.

antonkal: 2024-07-31 20:30:24

Naive solution:
Generate the sorted permutations, o(n!) time
Index the original list in the generator object

Any improvements?

cypher70: 2023-02-15 07:51:10

Use a big integer or any similar library because the answer will not fit in long datatype.

Vijai Shankar Natarajan: 2009-06-14 12:19:44

After the sort, in what position, with the lexiographically first list being in position 1, is his original spelling list?

What does this mean?

Paul Draper: 2009-06-01 16:16:03

I apologize. I have added an upper limit on the number of characters.
And lost, I don't know why you have that error. Do remember that there is a space at the end of each list of words (after the last word).

Last edit: 2009-06-01 16:18:54
lost: 2009-06-01 16:15:22

what is the maximum number of characters in a single word? Also please check whether the input file is according to the input specification or not. I am getting runtime error on using gets function, while using scanf results in TLE.


Added by:Paul Draper
Date:2009-05-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET