Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Anagrams

Two strings are considered anagrams if we can rearrange the letters of one to obtain the other. So, for instance, the words `listen` and `silent` are anagrams, as it’s possible to rearrange the letters of `listen` to obtain `silent`. Similarly, `William Shakespeare` is an anagram of `I am a weakish speller`. So, when determining if two strings are anagrams, the comparison should be case insensitive, and the two strings can have a different number of spaces.
Given a string `s` and `n` other strings, you are asked to calculate how many of those are anagrams of the string `s`.

#### Input

The first line of the input contains the string `s` (1 ≤ |s| ≤ ). The second line contains the number `n` (0 ≤ n ≤ ). The next `n` lines contain strings of lengths not exceeding 100.

#### Output

The program should print the number of anagrams of the string `s`.

#### Examples

 Input Output Tom Marvolo Riddle 2 Some random string I am Lord Voldemort 1

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB