# Compare those strings solution codechef

Contents

## Compare those strings solution codechef

Chef has two strings AA and BB consisting of lowercase alphabets, each of length NN. Help Chef in finding the number of indices ii (1iN)(1≤i≤N) such that A[iN]<B[iN]A[i…N]<B[i…N].

• S[iN]S[i…N] denotes the suffix of string SS starting at index ii, i.e. SiSi+1SiSi+1  SNSN.
• String S<S< String TT denotes that SS is lexicographically smaller than TT. If two strings SS and TT have the same length NN, we say that SS is lexicographically smaller than TT if there exists an index i(1iN)i(1≤i≤N) such that S1=T1,S1=T1, S2=T2,,Si1=Ti1S2=T2,…,Si−1=Ti−1 and Si<TiSi<Ti. For example, “abcabc” is lexicographically smaller than “acdacd“, “abeabe“, but not smaller than “abcabc“, “aacaac“. Compare those strings solution codechef ### Input Format

• The first line contains TT denoting the number of test cases. Then the test cases follow.
• The first line of each test case contains NN, denoting the length of the strings AA and BB.
• The second line of each test case contains the string AA.
• The third line of each test case contains the string BB.

### Compare those strings solution codechef Output Format

For each test case, print a single line containing one integer – the number of indices ii such that A[iN]<B[iN]A[i…N]<B[i…N].

### Constraints

• 1T1051≤T≤105
• 1N1061≤N≤106
• The sum of NN over all test cases does not exceed 106106

### Compare those strings solution codechef Sample Input 1

2
2
ab
bb
3
aaa
aab


### Sample Output 1

1
3


### Explanation Compare those strings solution codechef

Test Case 11:

• For i=1i=1A=A[1…2]= “abab“, B=B[1…2]= “bbbb” and lexicographically, “abab” << “bbbb“.
• For i=2i=2A=A[2…2]= “bb“, B=B[2…2]= “bb” and lexicographically, “bb” == “bb“.

Test Case 22: For each i{1,2,3}i∈{1,2,3}A[i3]<B[i3]A[i…3]<B[i…3].