Yesterday's number theory class was taught by Shiho a member of the Konoha Cryptanalysis Team. She taught the young ninjas Caesar Cipher Encryption and how it is used in real missions. Little Shikamaru found the method very genius and beautiful.
So, when he came home, he came up with the following problem. Given two strings of digits initial and target, he will take any substring of length K or smaller from the initial string, and apply a right shift of any length he wants. He will repeat this process until he fully converts it to the target string, or he will stop if he thinks it is impossible. Little Shikamaru would like to know the minimum number of moves required to complete the conversion.
Note About Right Shifts:
Shifting right by x, means substituting every digit by the xth digit after it, wrapping arround if needed. For example, when we shift "9" by 1, it will become "0".
Input Format:
Each test case starts with K the length of the substring. Second and third lines contain the initial and target strings, respectively.
Output Format:
Print the minimum number of moves in order to convert initial to target, else print 1 if it is impossible.
Constraints:
- 0≤K≤6
- Length of initial and target are less than or equal 50
- Length of initial and target is the same
Apply a right shift of length 1 to the first two characters, then your intial string will become [11 11]. The second move is to update the second and third characters again by a right shift of length 1 to get the final string.
