F. Factory TikTak Trend
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Maria Jose has recently started working at a new company in her town that is internationally renowned for printing cool, yet nonsensical text on T-shirts. These shirts have become a sensation on a platform called TikTak (For legal purposes of this statement). Maria Jose is also very popular on TikTak, but lately anyone using the "Pedro Pedro" trend seems to get more views than her. Seeking to stand out, she has decided to breach company policy by creating a behind-the-scenes video at the factory that makes these trending shirts.

At the start of each month, the factory selects two long strings, s and t, to print on a single T-shirt. Machine S is exclusively assigned string s and machine T is exclusively assigned string t. Each machine has a specific operation that it performs on its string after printing a shirt in order to create various patterns.

Machine S can be described in its i-th state, $$$S_i$$$, where it performs the following operation i times:

  • Removes the first character of s and appends it to the end of s.
Machine T can be described in its i-th state, $$$T_i$$$, where it performs the following operation i times:
  • Removes the last character of t and appends it to the beginning of t.
Maria Jose needs to give the final touch to her TikTak to get the maximum views possible, for that she has to add a curious cool fact about the most popular shirts in the world, and as is well known nothing is cooler than knowing what a string is lexicographically less than or equal to another string.

Maria Jose needs your help to find the number of distinct pairs $$$(i, j)$$$ such that $$$0 \leq i, j \leq N - 1$$$ where $$$S_i$$$ is lexicographically less than or equal to $$$T_j$$$.

Input

The first line contains an integer N $$$(1 \leq N \leq 2 \times 10^5)$$$, the length of the strings s and t.

The second line contains the string s, consisting of lowercase English letters.

The third line contains the string t, consisting of lowercase English letters.

Output

Print a single integer indicating the number of unique (i, j) pairs for which $$$S_i \leq T_j$$$.

Example
Input
3
bec
dbc
Output
4