QAQ, the greatest mathematician of the 21st century, found a new number called QAQ Number. The QAQ Numbers are positive integers without leading zeros which satisfy the following conditions:
-
It has exactly $3k$ digits(k is a positive integer), and can be divided into three sections $a_{1}...a_{k}$, $a_{k+1}...a_{2k}$ and $a_{2k+1}...a_{3k}$.
-
Digits of the same section are the same. Explicitly, $a_{1} = a_{2} = ... = a_{k - 1} = a_{k}$, $a_{k + 1} = a_{k + 2} = ... = a_{2k - 1} = a_{2k}$, $a_{2k + 1} = a_{2k + 2} = ... = a_{3k - 1} = a_{3k}$.
-
The first and third sections are the same, which means $a_{1} = a_{2k + 1}$, $a_{2} = a_{2k + 2}$ , ... , $a_{k} = a_{3k}$.
For instance, 111222111, 919 and 666666 are QAQ Numbers, but 1111, 010 , 444455554443 are not.
Now QAQ wants to know how many QAQ Numbers are there in range [L, R](inclusive).
