14435 - Orange Cat's Puzzle   

Description

Orange Cat(橘貓) loves playing with puzzles. Each puzzle consists of 26 letters, from a to z, and can be represented as a string.

When assembling the puzzles, Orange Cat refers to his instruction manuals. However, he accidentally mixed up the numbers of these instruction manuals. He had to arrange them randomly, but he can't determine if his arrangement is correct. Please write a program to tell him which instruction manuals correctly correspond to their respective puzzles.

The definition of an instruction manual correctly corresponding to a puzzle is: two strings can become the same after any rearrangement. For example, if Orange Cat matches the puzzle "abc" with an instruction manual containing "cba", then this correspondence is correct.

Input

The first line of input contains an integer n. n represents the number of puzzle-instruction manual pairs.

The following n lines each contain two strings, Ai and Bi, separated by a space. They represent the i-th puzzle and instruction manual, respectively.

 

Constraints

  • 1 ≤ n ≤ 500
  • All strings are composed of lowercase English letters.
  • 1 ≤ | Ai | = | Bi | ≤ 10000 (| | represents the length of string S)

Subtasks

  • Testcases 1: n = 1
  • Testcases 2 ~ 3: Characters within Ai , Bi are arranged in ascending lexicographic order.
  • Testcases 4 ~ 6: No additional restrictions.

Important: The method for comparing the lexicographic order of two strings is as follows: Starting from the first position (leftmost), find the first character that differs. The string with the smaller character at that position is considered lexicographically smaller. For example, 'abc' < 'abd' because the first differing letter 'c' < 'd'.

 

Output

Output a single integer representing the number of puzzle and instruction manual pairs that Orange Cat correctly matched.

 

Please remember to print "\n" at the end.

 

Sample Input  Download

Sample Output  Download

Tags




Discuss