Subwords is a game wherein you are given a word and must find all possible rearrangements of the letters that form English words.  Not all letters need be used.  For example, if you're given the word "computer" then four possible subwords are:

• Court
• Outer
• Truce
• Pure

Given an input word and a list of dictionary words, return the total number of valid subwords found.

Note that a word is not considered a subword of itself.  For example, with the input "computer" if you find "computer" in the dictionary then it should not be counted.

Additionally, a subword should not be counted twice if there are multiple ways to form that word.  For example, if your word is balloon then you should not count the word "on" twice using each 'o'.  It should be counted only once.

Input

The first string input is the starting word.  All remaining strings are the dictionary.  You should ignore any blank lines.  Note that you may need to be able to handle a long list of words (tens of thousands).

Output

The number of subwords found in the dictionary.

Example

Input:
computer

aardvark

computer

court

outer

pure

truce

wish

Output:
4