q1

Chef had a hard day and want to play little bit. The game is called "Chain". Chef has the sequence of symbols. Each symbol is either '-' or '+'. The sequence is called Chain if each two neighboring symbols of sequence are either '-+' or '+-'.

For example sequence '-+-+-+' is a Chain but sequence '-+-+--+' is not.

Help Chef to calculate the minimum number of symbols he need to replace (ex. '-' to '+' or '+' to '-') to receive a Chain sequence.

Input

• First line contains single integer T denoting the number of test cases.
• Line of each test case contains the string S consisting of symbols '-' and '+'.

Output

• For each test case, in a single line print single interger - the minimal number of symbols Chef needs to replace to receive a Chain.

Constraints

• 1 = T = 7
• 1 = |S| = 10^5

Subtasks

• Subtask 1 = |S| = 10, 1 = T = 7 Points: 20
• Subtask 1 = |S| = 1000, 1 = T = 7 Points: 30
• Subtask 1 = |S| = 10^5, 1 = T = 7Points: 50

Example

Input: 2 ---+-+-+++ ------- Output: 2 3

Explanation

Example case 1.

We can change symbol 2 from '-' to '+' and symbol 9 from '+' to '-' and receive '-+-+-+-+-+'.

Example case 2.

We can change symbols 2, 4 and 6 from '-' to '+' and receive '-+-+-+-'.

q2

Devu likes to play with a lock of N dials. Each dial rotates from numbers 0 to 9 clockwise (i.e. 0 to 1, 2 to 3 and 8 to 9). You can not rotate from 9 to 0.

Initially all the dials of the lock are set to 0. From the current lock, Devu can move any dial to at most 10 different positions (i.e. 0 to 9), so there are total 10^N different locks possible.

Let us say for a lock we define cost of converting the initial lock (all zeros) to this lock. For this, we have to rotate each dial to corresponding position in the lock. Cost of moving a single dial to value x takes x seconds.
eg. cost of moving to 123 is 1 + 2 + 3 = 6 and cost of moving to 99 is 9 + 9 is 18.

Now Devu has to hurry up to meet his girlfriend, So he has at most M seconds to spend, he wonders how many possible locks he can create such that when a lock is represented as a decimal number, it should be divisible by P. As answer could be large, print answer modulo 998244353.

Input

Only line of input will contain three integers N, P, MM respectively. Use of MM is defined in the output section.

Output

Print a single line containing MM + 1 integers, i^th (0 based indexing) of them should represent the
answer for the problem with given N, P and M = i.

Constraints

• Subtask #1: (10 points) 1 = N = 1000, 1 = P = 50, 1 = MM = 50 TL : 5 secs
• Subtask #2: (20 points) 1 = N = 10^9, 1 = P = 50, 1 = MM = 50 TL : 5 secs
• Subtask #3: (30 points) 1 = N = 10^9, 1 = P = 50, 1 = MM = 500 TL : 10 secs
• Subtask #4: (40 points) 1 = N = 10^9, 1 = P = 16, 1 = MM = 15000 TL : 15 secs

Example

Input: 2 3 3 Output: 1 1 1 5 Input: 2 4 4 Output: 1 1 2 3 5

Explanation

Example #1.
For M = 0, we can have only one lock, ie. all zeros 00, it is divisible by 3.
For M = 1, we can have only one lock, ie. all zeros 00, it is divisible by 3.
For M = 2, we can have only one lock, ie. all zeros 00, it is divisible by 3.
For M = 3, we can have 5 locks whose decimal representation is divisible by 3. They are 00, 03, 21, 30 and 12.

Example #2.
For M = 0, we can have only one lock, ie. all zeros 00, it is divisible by 4.
For M = 1, we can have only one lock, ie. all zeros 00, it is divisible by 4.
For M = 2, we can have 2 locks whose decimal representation is divisible by 4. They are 00 and 20.
For M = 3, we can have 3 locks whose decimal representation is divisible by 4. They are 00, 12 and 20.
For M = 4, we can have 5 locks whose decimal representation is divisible by 4. They are 00, 04, 12, 20 and 40.