Potassium, a genius who masters soul conversion, is observing the world line of Potas. The world line can be divided into nnn parts and represented as an n-digit decimal number s (may have leading zeros) that reveals the property of time in the past and future of Potas.
For convenience, let abc denote the concatenation of digits a,b,ca, b, ca,b,c, so the world line can be expressed as s=s1s2⋯sn. When observing, Potassium focuses on the era, which consists of continuous parts in the world line. An era beginning from part l to r can be denoted as slsl+1⋯sr(1≤l≤r≤n1), and may also have leading zeros.
When two eras are quite similar, Potassium can observe one from another by Spirit Circle. More specifically, an era B=sl2sl2+1⋯sr can be observed from another era A=sl1sl1+1⋯sr by Spirit Circle if and only if the following two conditions are satisfied, regardless of where A and B locate in s originally.
1. A and B have the same length, i.e. r1−l1+1=r2−l2+1;
2. B is greater than A by exactly 111, i.e. r1+1=sl2sl2+1⋯sr2.
Potassium is wondering: how many different pairs (A,B) can be found in sss that he can observe era B from era A. Note that two eras having the same representations but differing in the original location in sss are considered as different eras.