There are **N** cities in Chelsea's state (numbered starting from 1, which is Chelsea's city), and **M** bidirectional roads directly connect them. (A pair of cities may even be directly connected by more than one road.) Because of changes in traffic patterns, it may take different amounts of time to use a road at different times of day, depending on when the journey starts. (However, the direction traveled on the road does not matter -- traffic is always equally bad in both directions!) All trips on a road start (and end) exactly on the hour, and a trip on one road can be started instantaneously after finishing a trip on another road.

Chelsea loves to travel and is deciding where to go for her winter holiday trip. She wonders how quickly she can get from her city to various other destination cities, depending on what time she leaves her city. (Her route to her destination may include other intermediate cities on the way.) Can you answer all of her questions?

The first line of the input gives the number of test cases, **T**. **T** test cases follow.

The first line of each test case contains three integers: the number **N** of cities, the number **M** of roads, and the number **K** of Chelsea's questions.

2**M** lines -- **M** pairs of two lines -- follow. In each pair, the first line contains two different integers x and y that describe one bidirectional road between the x-th city and the y-th city. The second line contains 24 integers Cost[t] (0 ≤ t ≤ 23) that indicate the time cost, in hours, to use the road when departing at t o'clock on that road. It is guaranteed that Cost[t] ≤ Cost[t+1]+1 (0 ≤ t ≤ 22) and Cost[23] ≤ Cost[0]+1.

Then, an additional **K** lines follow. Each contains two integers **D** and **S** that comprise a question: what is the fewest number of hours it will take to get from city 1 to city **D**, if Chelsea departs city 1 at **S** o'clock?

For each test case, output one line containing "Case #x: ", where x is the case number (starting from 1), followed by **K** distinct space-separated integers that are the answers to the questions, in order. If Chelsea cannot reach the destination city for a question, no matter which roads she takes, then output -1 for that question.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ x, y ≤ **N**.

1 ≤ all Cost values ≤ 50.

1 ≤ **D** ≤ **N**.

0 ≤ **S** ≤ 23.

1 ≤ **T** ≤ 100.

2 ≤ **N** ≤ 20.

1 ≤ **M** ≤ 100.

1 ≤ **K** ≤ 100.

1 ≤ **T** ≤ 5.

2 ≤ **N** ≤ 500.

1 ≤ **M** ≤ 2000.

1 ≤ **K** ≤ 5000.

Sample Input

3 3 3 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 3 3 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 4 3 3 3 1 2 7 23 23 25 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 1 3 10 11 15 26 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 2 3 7 29 28 27 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 2 14 3 3 3 21

Sample Output

Case #1: 1 2 Case #2: 1 -1 Case #3: 17 26 13

A typical mountain bike has two groups of gears: one group connected to the pedals, and one group connected to the rear tire. A gear group consists of many gears, which usually have different numbers of teeth. A chain connects one of the gears in the pedal gear group to one of the gears in the tire gear group, and this determines the ratio between the cyclist's pedaling speed and the tire speed. For example, if the chain connects a gear with 5 teeth on the pedals to a gear with 10 teeth on the tires, the ratio will be 1/2, since the cyclist needs to make the pedal gear rotate twice to make the tire rotate once. The cyclist can change the chain to connect any one gear from the pedal group to any one gear from the tire group.

You have just bought a special new mountain bike with *three* groups of gears: one connected to the pedals, one connected to the tire, and one extra group in between. This mountain bike has two chains; the first chain must always connect one gear from the pedal gear group to one gear on the extra gear group, and the second chain must always connect one gear from the extra gear group to one gear on the tire gear group. Moreover, the two chains cannot both use the same gear from the extra gear group.

Given the numbers of teeth on the available gears on the pedals, extra, and tire groups, is it possible to make the ratio (between pedaling speed and tire speed) be exactly **P/Q**? For a given set of gears, you may need to answer multiple such questions.

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each begins with one line with 3 integers **N _{p}**,

For each test case, first output one line containing "Case #x:", where x is the test case number (starting from 1). Then output one line for each question within the test case, in the order that the questions were presented: `Yes`

if it's possible to make the ratio **P/Q**, and `No`

if it's impossible.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ the number of teeth on each gear ≤ 10000.

1 ≤ all values of **P**, **Q** ≤ 10^{9}.

1 ≤ **M** ≤ 10.

Time limit: 30 seconds.

1 ≤ **N _{p}, N_{t}** ≤ 10.

2 ≤

Time limit: 180 seconds.

1 ≤ **N _{p}, N_{t}** ≤ 2000.

2 ≤

Sample Input

1 1 2 3 5 4 6 3 5 7 2 1 1 5 2

Sample Output

Case #1: No Yes

For the second question in the test case, you can make the first chain connect the 5-tooth gear on the pedal gear group to the 4-tooth gear on the extra gear group, and make the second chain connect the 6-tooth gear on the extra gear group to the 3-tooth gear on the tire gear group. With this setup, the ratio is 5/2.

Googlers are crazy about numbers and games, especially number games! Two Googlers, Laurence and Seymour, have invented a new two-player game based on "gNumbers". A number is a gNumber if and only if the sum of the number's digits has no positive divisors other than 1 and itself. (In particular, note that 1 is a gNumber.)

The game works as follows: First, someone who is not playing the game chooses a starting number **N**. Then, the two players take turns. On a player's turn, the player checks whether the current number C is a gNumber. If it is, the player loses the game immediately. Otherwise, the player chooses a prime factor P of C, and keeps dividing C by P until P is no longer a factor of C. (For example, if the current number were 72, the player could either choose 2 and repeatedly divide by 2 until reaching 9, or choose 3 and repeatedly divide by 3 until reaching 8.) Then the result of the division becomes the new current number, and the other player's turn begins.

Laurence always gets to go first, and he hates to lose. Given a number **N**, he wants you to tell him which player is certain to win, assuming that both players play optimally.

The first line of the input gives the number of test cases, **T**. **T** test cases follow; each consists of a starting number **N**.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the winner's name: either `Laurence`

or `Seymour`

.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

Time limit: 30 seconds.

1 < **N** ≤ 1000.

Time limit: 60 seconds.

1 < **N** ≤ 10^{15}.

Sample Input

9 2 3 4 6 8 9 30 36300 1000000000000000

Sample Output

Case #1: Seymour Case #2: Seymour Case #3: Laurence Case #4: Laurence Case #5: Laurence Case #6: Laurence Case #7: Seymour Case #8: Laurence Case #9: Seymour

In Case #3, 4 is not a gNumber, since the sum of its digits is 4, which has a positive divisor other than 1 and itself (namely, 2). 4 has one prime factor (2), so Laurence must choose this factor and repeatedly divide 4 by it, which leaves him with 1. Then, Seymour begins his turn with 1, which is a gNumber. So he loses and Laurence wins.

The DNA of the Albocede alien species is made up of 4 types of nucleotides: ### Input

### Output

### Limits

#### Small dataset (Test Set 1 - Visible)

#### Large dataset (Test Set 2 - Hidden)

### Sample

`a`

, `b`

, `c`

, and `d`

. Different Albocedes may have different sequences of these nucleotides, but any Albocede's DNA sequence obeys all of the following rules:

- It contains at least one copy of each of
`a`

,`b`

,`c`

, and`d`

. - All
`a`

s come before all`b`

s, which come before all`c`

s, which come before all`d`

s. - There are exactly as many
`'a'`

s as`'c'`

s. - There are exactly as many
`'b'`

s as`'d'`

s.

For example, `abcd`

and `aabbbccddd`

are valid Albocede DNA sequences. `acbd`

, `abc`

, and `abbccd`

are not.

The Albocede-n is an evolved species of Albocede. The DNA sequence of an Albocede-n consists of one or more valid Albocede DNA sequences, concatenated together end-to-end. For example, `abcd`

and `aaabcccdaabbbccdddabcd`

are valid Albocede-n DNA sequences. (Observe that a valid Albocede-n DNA sequence is not necessarily also a valid Albocede DNA sequence.)

From one of your alien expeditions, you retrieved an interesting sequence of DNA made up of only `a`

s, `b`

s, `c`

s, and `d`

s. You are interested in how many of the different subsequences of that sequence would be valid Albocede-n DNA sequences. (Even if multiple different selections of nucleotides from the sequence produce the same valid subsequence, they still all count as distinct subsequences.) Since the result may be very large, please find it modulo 1000000007 (10^{9} + 7).

The first line of the input gives the number of test cases, **T**. Each of the next **T** lines contains a string **S** that consists only of the characters `a`

, `b`

, `c`

, and `d`

.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the output of the x^{th} test case.

Memory limit: 1 GB.

1 ≤ **T** ≤ 20.

Time limit: 30 seconds.

1 ≤ **length of S** ≤ 50.

Time limit: 120 seconds.

1 ≤ **length of S** ≤ 500.

Sample Input

5 abcd aaaabcd aaaabbccd abcdabcdaabccd b

Sample Output

Case #1: 1 Case #2: 4 Case #3: 28 Case #4: 71 Case #5: 0

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

The problem can be solved using Dynamic programming approach.

Test Data

We recommend that you practice debugging solutions without looking at the test data.