Peter and John are having fun with the the succession of Fibonacci numbers that fit on 64-bit signed integer. Fibonacci sequence is defined as: 1 if n = 0 if n = 1 if n ≥ 2 Fn = 1 Fn−1 + Fn−2 The first terms of the sequence are: 1, 1, 2, 3, 5, 8, 13, 21, and so on. After a while, Peter and John decided to create the concatfibos that are numbers built from the concatenation of two terms of the Fibonacci sequence, more formally, a term Fi and another Fk can be concatenated to create a concatfibo as FiFk or FkFi with i ̸= k. For example: Fi=8 Fk=55 They can be concatenated as FiFk = 855 or FkFi = 558. For example: Theconcatfibo213maycomefromFi =2andFk =13asFiFk =213orfromFi =21andFk =3 as FiFk = 213. Thus, they started to generate all the concatfibos without repetition (unique), and decided to create a greater challenge so John writes an alphanumeric string in which Peter must count the number of unique concatfibos that are contained as a subsequence of the given string. A string T is a subsequence of another string S if deleting some elements from S and without changing the order of the remaining elements, it is possible to get T. Help Peter discover how many unique concatfibos are contents as a subsequence of the given string. Input There are multiple test cases. Each test case contains a string S (1 ≤ |S| ≤ 106) consisting of lowercase and uppercase letters from English alphabet and digits between 0 and 9. Output For each test case, print exactly one line containing one integer representing how many unique con- catfibos are contents as a subsequence of the given string. Explanation: In the first test case, the concatfibos inside the string are 13, 15, 35, 134, 135 and 345. In the second test case, the string does not contain any concatfibo. Finally, in the third test case, the concatfibos inside the string are 13, 21, 23 and 213. Sample Input 1AB3RgtR4WkE5 AR4KD7 Scc2Ls1HjMg3K
2/2 Sample Output 6 0 4