Internet Problem Solving Contest

• Easy input data set – I1
• Hard input data set – I2

Number Man is one of the world’s most powerful superheroes, thanks to his superhuman mathematical powers. With a single thought he can forecast market movements, factor large numbers, extrapolate object trajectories, compute discrete logarithms, estimate probabilities of catastrophic events, and even calculate his tax rate. His favorite hobbies are knitting and high-frequency trading.

But despite his amazing powers, Number Man is very frustrated right now. His ultra-accurate weather prediction formula started giving ultra-inaccurate results, and he spent the last few hours searching for the cause. Did he really make a mistake? He never makes mistakes! And why does everyone else keep giggling? His teammates probably pranked him and made a tiny change on the blackboard while he was distracted. But what symbol did they change? There are so many options.

Problem specification

First, let’s recursively define what is a valid expression:

• A sequence of one or more digits is a valid expression. Leading zeros are allowed.
• If A is a valid expression, then (A) is a valid expression.
• If A and B are valid expressions, then A+B, A-B and A*B are valid expressions.
• Nothing else is a valid expression. No division, no unary minus, etc.

Number Man has a valid expression E. Every valid expression that has the exact same length as E and differs from E in exactly one character is a potentially correct expression. Note that E itself is not a potentially correct expression.

To calculate the weather value of a valid expression, calculate the expression’s value normally (standard precedence rules apply) and then find the nonnegative remainder that value gives modulo 10⁹ + 7. E.g. the weather value of “0-2*1” is 10⁹ + 5.

Find the weather value of every potentially correct expression. How many different numbers did you get?

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line and consists of a single line containing the incorrect but valid expression E.

In the easy subproblem I1, the length of each expression is at most 10 000.

In the hard subproblem I2, the length of each expression is at most 1 000 000.

Output specification

For each test case, print a single number: the number of distinct weather values among all potentially correct expressions.

Example

Input:

2

0+0

5*6*7

Output:

19
49