29260번 - THE iDEM@STER (M@STER VERSION)

문제

한별이는 문자 P와 @만을 사용하는 프로그래밍 언어를 만들었다.

한별이의 언어에서 올바른 프로그램을 이루는 문자열의 규칙은 다음과 같다.

• 모든 문자는 P와 @ 중 하나여야 하며, 같은 문자가 4ドル$번 이상 연속해서 등장하면 안 된다.
• 문자열에서 모든 PPP를 (로 바꾸고, @@@을 )로 바꾼 다음, 남아있는 P와 @을 지우면 올바른 괄호열이 되어야 한다.

이때 올바른 괄호열이란 다음과 같이 정의된다.

• 빈 문자열은 올바른 괄호열이다.
• $X$가 올바른 괄호열이면, $X$를 괄호로 감싼 ($X$)도 올바른 괄호열이다.
• $X$와 $Y$가 올바른 괄호열이면, $X$와 $Y$를 이어 붙인 $XY$도 올바른 괄호열이다.
• 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.

한별이의 언어는 프로그램을 실행하기 전에, 카운터 변수 $C$의 값을 0ドル$으로 초기화하고, 프로그램에 대해 전처리로 다음과 같은 과정을 순서대로 거친다.

• 프로그램의 모든 PPP를 (로 바꾼다.
• 프로그램의 모든 @@@을 )로 바꾼다.
• 프로그램에 남아있는 모든 P를 +로 바꾼다.
• 프로그램에 남아있는 모든 @을 -로 바꾼다.

예를 들어, 프로그램이 PPP@PP@PP@@@라고 하면, 전처리를 거친 후에는 (-++-++)이 된다.

전처리한 프로그램을 실행할 때, +는 $C$를 1ドル$ 증가시키고, -는 1ドル$ 감소시킨다. 한편, (와 )는 반복문으로, (와 ) 사이의 코드를 3ドル$ 번 반복해서 실행한다.

이를 의사코드로 표현하면 다음과 같다. 이때 문자열 $S$에 대해 $S[i]$ 는 $i$ 번째 문자를, $S[i..j]$는 문자열 $S$에서 $i$ 번째 문자부터 $j$ 번째 문자까지(경계 포함)의 부분 문자열을 의미한다.

Algorithm run(전처리한 프로그램 $S$)

• $i$를 1ドル$로 설정한다.
• while $i$ $\leq$ $S$의 길이
  • if $S[i]$가 +면
    • $C$를 1ドル$ 증가시킨다.
    • $i$를 1ドル$ 증가시킨다.
  • else if $S[i]$가 -면
    • $C$를 1ドル$ 감소시킨다.
    • $i$를 1ドル$ 증가시킨다.
  • else if $S[i]$가 (면
    • $j$를 $S[i]$와 짝이 맞는 )의 인덱스로 설정한다.
    • run($A[i+1..j-1]$)을 3ドル$ 회 실행한다.
    • $i$를 $j+1$로 설정한다.

정수 $N$에 대해서, 프로그램 실행 후 $C$의 값이 $N$인 길이가 가장 짧은 올바른 프로그램의 길이를 $f(N)$으로 정의하자. 두 정수 $L$과 $R$이 주어지면 다음과 같은 합을 구하여라.

$$\sum_{i=L}^{R}f(i)$$

입력

첫째 줄에 테스트케이스의 개수 $T$가 주어진다. (1ドル \leq T \leq 10,000円$)

각 테스트케이스마다 한 줄에 두 정수 $L$과 $R$이 주어진다. ($-10^{15} \leq L \leq R \leq 10^{15}$)

출력

각 줄마다 각 테스트케이스에 대해 구하는 합을 출력하라. 가능한 모든 입력에 대해서 각 테스트케이스의 답은 10ドル^{18}$ 이하임을 증명할 수 있다.

제한

힌트