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.
2M 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.
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
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 Np, Ne, and Nt, representing the numbers of gears on the pedals, extra, and tire groups. Then, three more lines follow. These contain Np, Ne, and Nt integers, respectively, representing the numbers of teeth on the different gears on the pedals, extra, and tire gear groups, respectively. (It is guaranteed that the numbers of teeth on the gears within a group are all distinct.) The next line after that consists of one integer, M, the number of questions. Finally, there are M lines, each with 2 integers, P and Q, representing the target ratio. (It is not guaranteed that this ratio is a reduced fraction.)
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 ≤ 109.
1 ≤ M ≤ 10.
Time limit: 30 seconds.
1 ≤ Np, Nt ≤ 10.
2 ≤ Ne ≤ 10.
Time limit: 180 seconds.
1 ≤ Np, Nt ≤ 2000.
2 ≤ Ne ≤ 2000.
1 1 2 3 5 4 6 3 5 7 2 1 1 5 2
Case #1: No Yes
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 ≤ 1015.
9 2 3 4 6 8 9 30 36300 1000000000000000
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
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:
a, b, c, and d.as come before all bs, which come before all cs, which come before all ds.'a's as 'c's.'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 as, bs, cs, and ds. 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 (109 + 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 xth 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.
5 abcd aaaabcd aaaabbccd abcdabcdaabccd b
Case #1: 1 Case #2: 4 Case #3: 28 Case #4: 71 Case #5: 0