Description

Consider a N * N * N lattice. One corner is at (0,0,0) and the opposite one is at (N, N, N). How many lattice points are visible from corner at (0,0,0)? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.

Input

The first line contains the number of test cases T. The next T lines contain an interger N.


Constraints:
T<=100 1<=N<=100

Output

Output T lines, one corresponding to each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Wireless communication has become a more and more popular issue in the EECS studies, even though almost all commercial applications are based on a “wired” backbone infrastructure. As the best engineer of the company Hexagonal Electrical eXample (HEX corp.), you are to solve the wire routing problem for the new wireless service of the company.

The HEX corp. is building a new wireless service in a city. As what we told you, the HEX corp. has decided where to build the Access Point (AP) for wireless communication. The APs are distributed depending on the population, geography, and some other issues, and then use the cable to connect them together. In order to keep the maintenance more easily, HEX corp. wishes to route the cables by the streets in the city. Except two ends of cable, any other parts on the cable are insulated. Therefore, two cables on the same street would not affect each other and not be merged into one cable.

The layout of streets in city is very special. There are 3 types of street, which are called type 1, type 2, and type 3. Within each type, streets are parallel. The distances between every 2 parallel streets are the same, and there must be 3 streets cross each intersection.

Any APs are built on the intersections of streets. Assume the length of each street segment is 1; the total cost of the routing is the sum of lengths of cables used. Any APs can be connected indirectly, i.e. if there is a cable connecting AP1 and AP2, and another cable connects AP2 and AP3, then AP1 and AP3 are connected.

You are to determine what is the minimum cost required to connect all APs, by telling the HEX corp. what is the minimum sum of lengths of cables required.

Input

There are several cases in the input. There is an integer T, T ≤ 100, in first line of input, which indicates the number of cases.

For each case following, the first line contains a number N, N ≤ 1000, which indicates the number of APs.

There are N lines following. For the i^th line of these lines, there are 3 integers, S_(i,1), S_(i,2), and S_(i,3), which indicate the streets of type 1, type 2, and type 3 which cross the intersection. All these numbers are between 1 and 1000.

Output

For each case, output one line with one integer to indicate the minimum cost of network.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Millions of years ago massive fields of ice carved deep grooves in the mountains of Norway. The sea filled these grooves with water. The Norwegian people call them fjords. This landscape of mountains and water is beautiful, but it makes traveling difficult. The usual scheme is: drive some kilometers, wait for a ferry, cross a fjord with the ferry, drive some more kilometers, and so on until the destination has been reached. To reach a destination as early as possible, most people have the following strategy: drive as fast as allowed (the maximum speed is 80 km/h) to the next ferry, and wait until it goes. Repeat until the destination has been reached.

Since driving fast requires more fuel than driving slow, this strategy is both expensive and harmful to the environment. The new generation of cruise control systems is designed to help. Given the route you want to go, these systems will gather information about the ferries involved, calculate the earliest possible time of arrival at the final destination, and calculate a driving scheme that avoids driving faster than needed. The systems will calculate your road speed so that you board the next ferry the moment it leaves.

Given a route (a sequence of road-pieces and crossings with ferries), you must write a program to calculate the minimal time it takes to complete this route. Moreover, your program must find a driving scheme such that the maximal driving speed at any point during the trip is as small as possible.

Input

The input file contains one or more test cases. Each test case describes a route. A route consists of several sections, each section being either a piece of road or a crossing. The first line in the description contains a single number s (s > 0), which is the number of sections in the route. The next s lines contain the descriptions of the sections. Every line describing a section starts with two names: the place of departure and the place of arrival, followed by either the word ‘road’ or the word ‘ferry’ indicating what kind of section it is. If the section is a road, its length (a positive integer) is given in km. For example:

Dryna Solholmen road 32

Lines describing ferry sections have more information. Following the word “ferry”, the duration of the ferry crossing, in minutes (a positive integer) is given. This is followed by the frequency f (f > 0) of the ferry, that is, the number of times the ferry departs in a single hour. The next f integers give the departure times of the ferry, in ascending order. For example:

Manhiller Fodnes ferry 20 2 15 35

The ferry travels from Manhiller to Fodnes in 20 minutes, and it leaves twice an hour (on 0h15, 0h35, 1h15, 1h35,…). The beginning of the entire trip always starts at a full hour. The sections in a route are consecutive, that is, if a section goes from A to B then the next section starts at B. Every route in the input can be traveled in no more than 10 hours.

The input is terminated by the number zero on a line by itself.

Output

Output for each test case is a single line containing three items. The first item is the test case number. The second is the total travel time for an optimal scheme in the form hh:mm:ss. The third item is the maximal road speed in an optimal scheme rounded to two digits to the right of the decimal point.

Place a blank line after the output of each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In our increasingly interconnected world, it has been speculated that everyone on Earth is related to everyone else by no more than six degrees of separation. In this problem, you must write a program to find the maximum degree of separation for a network of people.

For any two people, the degree of separation is the minimum number of relationships that must be traversed to connect the two people. For a network, the maximum degree of separation is the largest degree of separation between any two people in the network. If there is a pair of people in the network who are not connected by a chain of relationships, the network is disconnected.

As shown below, a network can be described as a set of symmetric relationships each of which connects two people. A line represents a relationship between two people. Network A illustrates a network with 2 as the maximum degree of separation. Network B is disconnected.

Network A: Max. degree of separation = 2 Network B: Disconnected

Input

The input consists of data sets that describe networks of people. For each data set, the first line has two integers: P (2≤P≤50), the number of people in the network, and R (R≥1), the number of network relationships. Following that first line are R relationships. Each relationship consists of two strings that are names of people in the network who are related. Names are unique and contain no blank spaces. Because a person may be related to more than one other person, a name may appear multiple times in a data set.

The final test case is followed by a line containing two zeroes.

Output

For each network, display the network number followed by the maximum degree of separation. If the network is disconnected, display `DISCONNECTED'. Display a blank line after the output for each network. Use the format illustrated in the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Kim is a professional programmer. Recently he wants to design a new editor which has as many functions as possible. Most editors support a simple search function that finds one occurrence (or all occurrences successively) of a query pattern string in the text.

He observed that the search function in commercial editors does nothing if no query pattern is given. His idea of a new search function regards each substring of the given text as a query pattern string itself and his new function finds another occurrence in the text. The problem is that there can be occurrences of many substrings in the text. So, Mr. Kim decides that the new function finds only occurrences of the longest substring in the text in order to remedy the problem. A formal definition of the search function is as follows:

Given a text string S , find the longest substring in text string S such that the substring appears at least twice. The two occurrences are allowed to overlap.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. For each test case, a text string S is given in one line. For every string, the length is less than or equal to 5,000 and the alphabet Σ is the set of lowercase English characters.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print the length of the longest substring in text string S such that the substring appears at least twice.

Sample Input  Download

Sample Output  Download

Tags

Discuss