16진수 쪼개기

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

• 1 ≤ k ≤ n
• 1 ≤ i ≤ k인 각 i에 대해 부분문자열 Ti의 길이는 1 이상이고 S의 부분문자열이다. 즉, S에서 연속한 문자들로 이루어진다.
• T1, T2, ..., Tk를 순서대로 이어붙이면 원래 문자열 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가 비감소수열이 되는 경우가 몇 가지인지 알고 싶다. 구체적으로, 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"인 경우 다음 네 가지 방법이 가능하다.

• 방법 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을 포함하는 것도 허용된다.

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

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

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

문자열 S를 이루는 문자는 16진법에 쓰이는 0-9와 A-F뿐이다.

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

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