석표는 평소에 문자열을 가지고 노는 것을 좋아한다. 다음 조건을 만족하는 두 문자열은 닮았다고 한다.

1. 두 문자열이 같은 길이를 가지고 있다.

2. 길이 내의 모든 정수쌍 (i, j) 에 있어서, a[i]==a[j]이면 b[i]==b[j]이고, a[i]!=a[j]이면, b[i]!=b[j]이다.

예를 들어, a = ”adba”와 b = ”bcgb”는 닮았다. i=0이고, j=3이면, a[0] == a[3]이고 b[0]==b[3]이다.

다른 (i, j)쌍을 고르면, a에서도 b에서도 서로 다르다.

석표는 문자열 S를 가지고 있다. 심심했던 석표는 S의 부분문자열[l, r]과 닮은 부분문자열이 총 몇 개 있나 알아보고 싶다.

부분문자열[l, r]이란, S의 l번 인덱스부터 r번 인덱스까지의 연속된 문자열이다.

각 q개의 l과 r에 있어서, 부분문자열[l, r]과 닮은 S의 부분문자열의 수를 모두 출력하는 프로그램을 작성하라.

닮은 문자열 timer 1s memory 256MB

닮은 문자열 1s 256MB