STSTRING - Strings

Given two strings A and B, we define the operator ĉ on {A, B} for string C as C ĉ {A, B}.

if length(A) < length(C) < length(B), then C satisfies the above operator.
else
      if length(A)=length(C), then C must be lexicographically greater than A.
      if length(B)=length(C), then C must be lexicographically smaller than B.

Input

Given two strings A and B with length(A) <= length(B) <= 6. A and B can contain any characters between A and J (capital letters).

Output

Print the number of strings satisfying the above criteria. C must also satisfy criteria of A and B. Any two adjacent characters in string C may neither be the same nor consecutive (i.e. the absolute difference between the ASCII values of adjacent characters is greater than 1).

Example

Input:
A J
AA BCD
ABC DEFG

Output:
8
129
1770

Added by:eleusive
Date:2008-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2008 - Set by FameofLight and Challenger

hide comments
2009-04-29 23:23:58 Ahmed Kamel [ahm.kam_92]
"Given two strings A,B with length(A) < = length(B) <= 6"

Length of A will always be smaller than or equal length of B.
2009-04-25 00:13:52 Paul Draper
Your statement makes no statement about the case length(A)>length(C)>length(B).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.