Given two numbers $a$ and $b$, we proceed to construct a new number $c$ by using the digits of $a$ one by one from left to right. In each turn, we can choose to place the current digit to the left or right of the current $c$ (excluding the first turn). For example, if $c$ is currently $38182$ and we are considering the digit $1$, placing it to the left will make $138182$, and placing it to the right will make $381821$. The newly formed number $c$ is allowed to have the digit $0$ at the beginning.
A number is considered beautiful if it does not exceed the value of $b$. Calculate the sum of all beautiful numbers constructed in this way. Two numbers are considered different if their construction methods differ, even if they have the same value.
### Input
- The first line contains a natural number $T$, representing the number of test cases.
- Each group of lines that follows consists of a string $a$, containing only digits, and a natural number $b$.
### Output
- For each test case, print a number representing the sum of beautiful numbers modulo $10^9+7$.
### Constraints
- $T \le 50$.
- $|a| \le 500$.
- $b \le 10^{500}$.
### Example
Input:
```
1
1013
3000
```
Output:
```
3242
```
