16진수 쪼개기

길이가 n인 문자열 S를 아래 조건에 따라 k개의 부분문자열 (substring) T1, T2, ..., Tk로 쪼개는 경우를 생각해보자:

• 1 ≤ k ≤ n
• 1 ≤ i ≤ k를 만족하는 i에 대하여 각 부분문자열 Ti는 길이 1 이상이며 S의 부분문자열이다 (즉, S를 구성하는 연속한 문자들로 구성되어있다).
• T1, T2, ..., Tk 를 순서대로 이어붙이면 (string concatenation) 원래의 문자열 S가 된다.

예를 들어 S = "FED" 인 경우 아래와 같은 총 4가지의 방법으로 쪼갤 수 있다:

• 방법 1: T1 = "FED" (이 경우, k = 1)
• 방법 2: T1 = "F", T2 = "ED" (이 경우, k = 2)
• 방법 3: T1 = "FE", T2 = "D" (이 경우, k = 2)
• 방법 4: T1 = "F", T2 = "E", T3 = "D" (이 경우, k = 3)

참고로 길이가 n인 문자열을 위 조건대로 쪼개는 방법은 총 2n-1 가지 존재한다.

이 문제에서는 원래의 문자열 S가 0-9와 A-F로만 구성된 16진수라 가정한다.

Albert는 위 조건대로 S를 쪼개서 T1, T2, ..., Tk가 비감소수열이 (non-decreasing sequence) 되는 경우가 몇 가지나 되는지 알고 싶다.
구체적으로, Albert는 S를 쪼갠 후 각 부분 문자열이 타나내는 16진수 값이 T1 ≤ T2 ≤ ... ≤ Tk 를 만족하도록 하고 싶다.

위 예제의 경우, 상기한 네 가지 방법을 통해 만들어지는 수열은 아래와 같다:

• 방법1: [FED(16) = 4077] (비감소수열)
• 방법2: [F(16) = 15, ED(16) = 237] (비감소수열)
• 방법3: [FE(16) = 254, D(16) = 13]
• 방법4: [F(16) = 15, E(16) = 14, D(16) = 13]

이 경우 비감소수열은 방법1, 방법2을 통해 얻을 수 있으므로 답이 2가 된다.

다른 예로 S = "0070"인 경우, 아래와 같은 4가지 방법이 가능하다.

• 방법 1: T1 = "0070"
• 방법 2: T1 = "0", T2 = "0", T3 = "70" (이 경우 [0, 0, 70(16) = 112] 이다)
• 방법 3: T1 = "00", T2 = "70"
• 방법 4: T1 = "0", T2 = "070"

방법1, 방법3, 방법4에서 보이듯 부분 문자열이 선행 0을 (leading zero) 포함하는 것도 허용된다.

입력으로 16진수 문자열 S가 주어졌을 때, Albert가 몇 가지 방법으로 S를 부분 문자열로 쪼개서 비감소수열을 얻을 수 있는지 구해보자.

첫 줄에 테스트 케이스의 수 T가 주어진다. 

다음 각 줄에 문자열 S가 주어진다.

문자열 S를 구성하는 문자는 16진법에 사용되는 0-9 (숫자)와 A-F (영대문자) 뿐이다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• 1 ≤ T ≤ 20
• 1 ≤ n ≤ 15
• S를 구성하는 문자는 0-9 와 A-F 뿐이다