Groups of anagram product codes

Problem

A catalogue has n product codes made of lowercase letters. Two codes belong to the same group if one can be rearranged into the other. Print how many different groups there are. Comparing every pair of codes is too slow.

Input, output and limits

Input: Line 1: the integer n. Line 2: n codes separated by spaces.
Output: One integer: the number of groups.
Constraints: 1 ≤ n ≤ 50000
Each code has 1 to 20 lowercase letters

Examples

Example

Input

5
listen silent enlist google gogole

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Comparing every pair of codes costs n² letter comparisons.

Hint 2

Two codes are in one group exactly when their sorted letters are equal. Use the sorted letters as a key.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Customers in both reportsmedium
Marks at or below a scoremedium
Range totals of daily salesmedium
Ways to climb the warehouse stairsmedium
Count pairs with a target totalmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Time & Space Complexity problems

Problem

Input, output and limits

Examples

Hints

More Time & Space Complexity problems