Facebook her yıl HackerCup adında bir yarışma düzenliyor. Her ne kadar programlama yarışması dediysem de sadece programlama bilgisini değil algoritma kurabilme yeteneğini ve matematik bilgisini de ölçüyor.

Eleme turu için 3 soru verip 3 gün de süre tanıdılar. Eleme turundaki üç sorudan ikisini çözebildim. Çözümlerim aşağıda.

Neyse ki çözemediğim Auction sorusunu sadece 28 kişi çözebilmiş, ben de kendimi çok kötü hissetmedim 🙂

**Billboards**

We are starting preparations for Hacker Cup 2013 really early. Our first step is to prepare billboards to advertise the contest. We have text for hundreds of billboards, but we need your help to design them.

The billboards are of different sizes, but are all rectangular. The billboard widths and heights are all integers. We will supply you with the size in inches and the text we want printed. We want you to tell us how large we can print the text, such that it fits on the billboard without splitting any words across lines. Since this is to attract hackers like yourself, we will use a monospace font, meaning that all characters are of the same width (e.g.. ‘l’ and ‘m’ take up the same horizontal space, as do space characters). The characters in our font are of equal width and height, and there will be no additional spacing between adjacent characters or adjacent rows. If you print a word on one line and print the next word on the next line, you do not need to print a space between them.

Let’s say we want to print the text “Facebook Hacker Cup 2013″ on a 350×100″ billboard. If we use a font size of 33” per character, then we can print “Facebook” on the first line, “Hacker Cup” on the second and “2013” on the third. The widest of the three lines is “Hacker Cup”, which is 330″ wide. There are three lines, so the total height is 99″. We cannot go any larger.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case in the form “W H S”. W and H are the width and height in inches of the available space. S is the text to be written.

Output

Output T lines, one for each test case. For each case, output “Case #t: s”, where t is the test case number (starting from 1) and s is the maximum font size, in inches per character, we can use. The size must be an integral number of inches. If the text does not fit when printed at a size of 1″, then output 0.

Constraints

1 ≤ T ≤ 20

1 ≤ W, H ≤ 1000

The text will contain only lower-case letters a-z, upper-case letters A-Z, digits 0-9 and the space character

The text will not start or end with the space character, and will never contain two adjacent space characters

The text in each case contains at most 1000 characters

**Auction**

You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).

We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though.

One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator.

If product i has price Pi and weight Wi, then the following holds for product i+1:

Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)

Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)

You carefully calculated the parameters for the generator (P1, W1, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P1, W1, M, K, A, B, C and D.

Output

Output T lines, one for each test case. For each case, output “Case #t: a b”, where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 1018

1 ≤ M, K ≤ 107

1 ≤ P1 ≤ M

1 ≤ W_1 ≤ K

0 ≤ A,B,C,D ≤ 109

**Alphabet Soup**

Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.

Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase “HACKERCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word “HACKERCUP” side-by-side using the letters in his soup.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with a sequence of upper-case letters and spaces: the original sentence Alfredo constructed.

Output

Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “HACKERCUP” can be placed side-by-side using the letters from the sentence.

Constraints

1 < T ≤ 20

Sentences contain only the upper-case letters A-Z and the space character

Each sentence contains at least one letter, and contains at most 1000 characters, including spaces