[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

In the novel "A for Andromeda", by Fred Hoyle and John Elliot, a civilization from a planet in orbit around a star in the constellation of Andromeda, 200 light years away from our Solar System, decides to colonize the galaxy. To avoid the long and costly interstellar travels, this civilization decides to perform the colonization at a distance, by sending a signal instead of ships (this signal contains instructions on how to build a supercomputer with an artificial intelligence capable of taking over the world of the unfortunate civilizations who build it, but that is not our problem for the moment).

One of the issues humans have to overcome in order to construct the supercomputer is the decoding of the signal. As it happens, the aliens send two messages in two different frequencies, repeating endlessly in each of them a code with N characters. For example, if N = 3 and one of the codes is "abc", the alien message in the corresponding frequency will be "...cabcabcabcab...", where the ellipsis mean that the code is repeated infinitely both backwards and forwards. For this reason, the terrestrial stations receiving the signal are incapable of telling what the emitted code actually is, as there can be more than one code that is compatible with a given message. In our example, knowing that N = 3 they could interpret that the code is any of three possibilities "abc", "bca" and "cab".

Complicating matters even further, although both messages are composed solely of characters from the alphabet 'a' through 'z', because they are transmitted in different frequencies there exists an ambiguity in the identification of the characters between them. Thus, if we let the characters be named c₁ = 'a', c₂ = 'b', and so on until c₂₆ = 'z', it is possible that every occurrence of the character c_i in one of the messages is replaced by the character c_σ(i) in the other message, where σ(i) is an arbitrary permutation of the numbers from 1 to 26. For instance, if we have σ(1) = 24, σ(2) = 25 and σ(3) = 26 the code "abc" in one of the frequencies will be turned in the other into "xyz", so that the corresponding message will be "...zxyzxyzxyzxy...".

You've been put in charge of decoding the alien signal, and your task is to determine the maximum length of a common substring that two codes compatible with the received messages can have. This is, you should find the maximum value K such that one of the messages is compatible with the code a₁ a₂ ... a_N and the other is compatible with the code b₁ b₂... b_N, and there exist i and j with 0 ≤ i, j ≤ N-K such that a_i+k = b_j+k for k = 1, ..., K up to a permutation of the alphabet.

Input

There are multiple test cases in the input file. For each test case, the first line contains an integer N representing the length of the codes emitted by the aliens (1 ≤ N ≤ 1000). Each of the two following lines contains the description of the message received in a different frequency, in the form of a string of N characters from 'a' to 'z'. The received message is obtained repeating endlessly the corresponding string.

Output

For each test case, print one line containing an integer representing the maximum length of a common substring two codes which are compatible with the received messages can have.

Example

Input:
3
abc
xyz
3
aab
cdd
4
abab
xyzw
4
xyzw
abab
18
imzbyqlgjwrvfspthe
rubihyvjnomqdznhat

Output:
3
3
2
2
16