Facebook Hacker Cup 2011 Round 1C

Polynomial Factoring

A polynomial in x of degree D can be written as:

aDxD + aD-1xD-1 + ... + a1x1 + a0

In some cases, a polynomial of degree D can also be written as the product of two polynomials of degrees D₁ and D₂, where D = D₁ + D₂. For instance,

4 x2 + 11 x 1 + 6 = (4 x1 + 3) * (1 x1 + 2)

In this problem, you will be given two polynomials, denoted F and G. Your task is to find a polynomial H such that G * H = F, and each a_i is an integer.

Input

You should first read an integer N ≤ 60, the number of test cases. Each test case will start by describing F and then describe G. Each polynomial will start with its degree 0 ≤ D ≤ 20, which will be followed by D+1 integers, denoting a₀, a₁, ... , a_D, where -10000 ≤ a_i ≤ 10000. Each polynomial will have a non-zero coefficient for it’s highest order term.
]

Output

For each test case, output a single line describing H. If H has degree D_H, you should output a line containing D_H + 1 integers, starting with a₀ for H. If no H exists such that G*H=F, you should output “no solution”.

Sample input:

5

2 6 11 4
1 3 4
2 1 2 1
1 1 1
2 1 0 -1
1 1 1
1 1 1
2 1 2 1
5 1 1 1 1 1 1
3 1 1 1 1

Sample output:

2 1
1 1
1 -1
no solution
no solution

N-Factorful

A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers a, b, and n, your task is to find the number of integers between a and b, inclusive, that are n-factorful. We consider 1 to be 0-factorful.

Input

Your input will consist of a single integer T followed by a newline and T test cases. Each test cases consists of a single line containing integers a, b, and n as described above.

Output

Output for each test case one line containing the number of n-factorful integers in [a, b].

Constraints

T = 20
1 ≤ a ≤ b ≤ 10⁷
0 ≤ n ≤ 10

sample input

5
1 3 1
1 10 2
1 10 3
1 100 3
1 1000 0

sample output

2
2
0
8
1

Risky Slide

Being a confident and accomplished programmer, you are naturally widely considered to be one of the preeminent dancers of your generation. Unfortunately this means your dancing is under considerable public scrutiny, and your critics are often quick to point out when your moves seem to be getting stale. To prevent such a debacle, you are working on a new maneuver you’re calling “the risky slide”.

You haven’t worked out some of the details like flourishes or vocalizations that will accompany the risky slide, but you do know that the core of the move is a standing slide across a stretch of dance floor. You need to perfect the execution of your slide, so you are looking for the ideal spot in your apartment to practice.

You live a fairly ascetic lifestyle, so your apartment is a simple rectangle with a tiled floor and no furniture or contents of any kind. You will practice the risky slide by starting out standing at the edge of some tile and running parallel to one of the walls of the apartment, and at the transition between some pair of tiles you will go from running to sliding. Your goal is to achieve the longest possible slide, with distance measured as the number of tiles you completely traverse during the slide (partial traversal doesn’t count).

This would be an easy problem, but the style of the tiles in your apartment introduces a complication. Each tile has a particular stickiness that affects both how well you can run and how well you can slide on it. Each tile has a stickiness rating between 1 and 9, inclusive. The stickiness affects your movement as follows:
Running across a tile with stickiness s grants s units of kinetic energy. For example, a tile with stickiness 9 is not slippery at all and you can run across it very efficiently, whereas a tile with stickiness 1 is quite slippery and does not help you increase your kinetic energy much as you run across it.
Sliding across a tile with stickiness s robs you of s units of kinetic energy. If a tile would reduce your kinetic energy below 0, you stop sliding somewhere in the middle of the tile and fail to traverse it completely.]

Input

Your input will consist of a single integer N followed by a newline and N test cases. Each case begins with a line containing integers R and C, the number of rows and columns, respectively, of tiles in your apartment. This will be followed by R lines, each containing a string of length C, describing the layout of the tiles in your apartment. The value of each element in these strings is the stickiness as defined above of the corresponding tile.

Output

Output, for each test case and separated by newlines, the maximal possible number of complete tiles that you can traverse in a single slide through your apartment.

Constraints

N ≤ 20
1 ≤ R, C ≤ 50
Characters representing tiles will all be between ’1′ and ’9′, inclusive.

sample input

5

1 1
5
2 3
112
324
5 5
55555
51115
51915
51115
55555
1 4
5222
1 5
52222

sample output

0
2
3
2
3