Description

An organic compound is any member of a large class of chemical compounds whose molecules contain carbon. The molar mass of an organic compound is the mass of one mole of the organic compound. The molar mass of an organic compound can be computed from the standard atomic weights of the elements.

When an organic compound is given as a molecular formula, Dr. CHON wants to find its molar mass. A molecular formula, such as C₃H₄O₃ , identifies each constituent element by its chemical symbol and indicates the number of atoms of each element found in each discrete molecule of that compound. If a molecule contains more than one atom of a particular element, this quantity is indicated using a subscript after the chemical symbol.

In this problem, we assume that the molecular formula is represented by only four elements, `C' (Carbon), `H' (Hydrogen), `O' (Oxygen), and `N' (Nitrogen) without parentheses.

The following table shows that the standard atomic weights for `C', `H', `O', and `N'.

For example, the molar mass of a molecular formula C₆H₅OH is 94.108 g/mol which is computed by 6 × (12.01 g/mol) + 6 × (1.008 g/mol) + 1 × (16.00 g/mol).

Given a molecular formula, write a program to compute the molar mass of the formula.

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. Each test case is given in a single line, which contains a molecular formula as a string. The chemical symbol is given by a capital letter and the length of the string is greater than 0 and less than 80. The quantity number n which is represented after the chemical symbol would be omitted when the number is 1 (2 ≤ n ≤ 99) .

Output

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the molar mass of the given molecular formula.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a tree network with n nodes where the internal nodes correspond to servers and the terminal nodes correspond to clients. The nodes are numbered from 1 to n . Among the servers, there is an original server S which provides VOD (Video On Demand) service. To ensure the quality of service for the clients, the distance from each client to the VOD server S should not exceed a certain value k . The distance from a node u to a node v in the tree is defined to be the number of edges on the path from u to v . If there is a nonempty subset C of clients such that the distance from each u in C to S is greater than k , then replicas of the VOD system have to be placed in some servers so that the distance from each client to the nearest VOD server (the original VOD system or its replica) is k or less.

Given a tree network, a server S which has VOD system, and a positive integer k , find the minimum number of replicas necessary so that each client is within distance k from the nearest server which has the original VOD system or its replica.

For example, consider the following tree network.

In the above tree, the set of clients is {1, 6, 7, 8, 9, 10, 11, 13}, the set of servers is {2, 3, 4, 5, 12, 14}, and the original VOD server is located at node 12.

For k = 2 , the quality of service is not guaranteed with one VOD server at node 12 because the clients in {6, 7, 8, 9, 10} are away from VOD server at distance > k . Therefore, we need one or more replicas. When one replica is placed at node 4, the distance from each client to the nearest server of {12, 4} is less than or equal to 2. The minimum number of the needed replicas is one for this example.

Input

Your program is to read the input 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. The first line of each test case contains an integer n (3 ≤ n ≤ 1, 000) which is the number of nodes of the tree network. The next line contains two integers s (1 ≤ s ≤ n) and k (k ≥ 1) where s is the VOD server and k is the distance value for ensuring the quality of service. In the following n - 1 lines, each line contains a pair of nodes which represent an edge of the tree network.

Output

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer that is the minimum number of the needed replicas.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The city of Songpa is now carrying out a project to build a bicycle transportation system called ‘green Songpa.’ By the end of this year, citizens and visitors alike will be able to pick up and drop off bicycles throughout the city. Recently, it was decided to attach a number tag to each bicycle for management use. The bicycles will be under control of the city’s traffic system.

The number tag contains a tile code of length n , which consists of 1×2 , 2×1 , and 2×2 tiles placed on a 2×n rectangular plate in a way that every cell of the plate is covered by exactly one tile. The plate is divided into 2n cells of size 1×1 . Of course, no two tiles are allowed to overlap each other. The 2×5 plate and a tile code of length 5 are shown in Figures 1 and 2, respectively. The code will always be read from left to right. However, there is no distinction between the top side and the bottom side of the code. The code may be turned upside down. The code shown in Figure 3 is essentially the same code as in Figure 2.

Given a positive integer n , the project director Dr. Yang wants to know how many tile codes of length n there are, that is, the number of ways to place the three kinds of tiles into a 2×n rectangular plate subject to the above conditions. Write a program that can help him.

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. Each test case is given in a single line, which contains a positive integer n , 3 ≤ n ≤ 30 .

Output

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the number of tile codes of length n .

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Let DC (direct current) circuits be given. Each DC circuit generates a set of output signals. The DC circuits consist of a set of devices connected in parallel or in serial but they have no feedback loops. Each device generates a specific signal and the set of output signals of a circuit is determined by the kinds of devices and the topology of the device connection. For example, let two circuits named C1 and C2 be given as follows:

For C1, two signals, namely abc and adc can be generated. Given a circuit C, the output OUT(C) of it is defined as the set of signals which can be generated by C. For C1, the output of C1 is {abc, adc}, i.e. OUT(C1) = {abc, adc}. By the way, OUT(C2) is also {abc, adc}. For the above circuits, OUT(C1) = OUT(C2).

There is a special device called the pass device, namely 1, generating no signal at all. The circuit C3 contains a pass device. The parallel connections and serial connections of sub-circuits can be arbitrarily nested and composed as shown in circuit C4.

For C3, the output is {abc, ac}, i.e. OUT(C3) = {abc, ac}; for C4, the output is {abc, aabc, aadc}, i.e. OUT(C4) = {abc, aabc, aadc}.

The problem is to determine the relation of two given circuits. The names of normal devices are given by lowercase letters depending on the signals generated by them. The name of the pass device is 1. The parallel connection of two circuits C and D is denoted by C| D and the serial connection of two circuits C and D in a row is denoted by CD . The parentheses can be used as needed to clarify the topology of connections, but no spaces are allowed in a circuit description.

For example, the denotations of the above circuits are given as follows:

There can be redundant parentheses around the representation of sub-circuits. For instance, C1 can be represented by (a((b)|((d)))c) instead of a(b|d)c.

The comparison result of two circuits is denoted by =, <, >, 0, and 1. Given two circuits C and D , the relation between them is determined as follows:

Assume that every circuit generates at least one signal. In other words, there’s no circuit whose output is {} though it is allowed for nested circuits such as 1 or (1|1).

Input

Your program is to read the input 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. Each test case is given by two circuit representations separated by one or more spaces. The length of a circuit representation is less than 50; and the number of test cases is less than 30.

Output

Your program is to write to standard output. For an input test case representing two circuits C and D in sequence, print a character representing the relation of C and D in one line. Hence, the number of output lines is equal to the number of test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are going to draw a figure on a monitor using a keyboard of a computer. The figure which you want to draw is a polygonal chain which consists of horizontal or vertical line segments only. In order to draw the figure, you should press some keys successively. A sequence of keys consists of pairs of a direction key and a digit key. The direction keys consist of four keys which are labeled as `N', `S', `E', and `W'. The symbols `N', `S', `E', and `W' represent North, South, East, and West respectively. The digit keys consist of 10 keys which are labeled as `0', `1' , ... , `9'.

Initially, the cursor is located at the center of a monitor screen. If you will enter ``S4E3", i.e. you’ll press the keys `S', `4', `E', and `3' in order, an L-shaped chain will appear on the monitor. When you first press the two keys `S' and `4', a vertical line segment with length 4 from the current cursor position, i.e. the center of the screen, to the south is drawn and the cursor is located at the endpoint of that segment. When you press next the two keys `E' and `3', a horizontal line segment with length 3 from the current cursor position to the east is drawn.

Your computer program always keeps the polygonal chain simple. In other words, the polygonal chain on the monitor doesn’t have either a cycle or an overlapped segment. Whenever the program finds a cycle or an overlap in the drawing, it instantly gets rid of it. For example, if you enter ``E6S2W5S2E2N7", two intersection points p and q occur in order by the last segment (see Figure 1). The program first gets rid of the cycle (p, d, e, f ) containing the intersection p , then the cycle (q, b, c, p) containing q as shown in Figure 1. Hence, the resulting chain on the monitor is the same as the chain by ``E3N3". If you enter ``E4S2W3S2E6N6W4S7", the program gets rid of the cycle (p, b, c, d, e, f, g, h) created by the first intersection point p as shown in Figure 2 (a). After removing this cycle, the other intersections disappear. The resulting chain is the same as that by ``E3S5". If you enter ``N5S9"(resp. ``! N9S5"), the resulting chain is identical to that by ``S4"(resp. ``N4") as shown in Figure 2 (b).

Given a sequence of keys, write a program for computing the resulting chain. You can assume that the size of the monitor screen is sufficiently large.

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. Each test case is given in a single line, which contains a string d₁f₁d₂f₂...d_nf_n , where d_i ∈ {`N', `S', `E', `W'}, fi ∈ {`0', `1', ... , `9'}, and 1 ≤ n ≤ 5, 000 .

Output

Your program is to write to standard output. Print exactly one line for each test case. Print two integers m and L , where m is the number of line segments on the resulting chain and L is the length of that chain, i.e. the total sum of the lengths of all line segments on the chain.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The game of Tic Tac Toe is played on an n-by-n grid (where n is usually but not necessarily three). Two players alternate placing symbols on squares of the grid. One player places Xes and the other player places Os. The player placing Xes always goes first. When the grid contains a vertical, horizontal, or diagonal sequence of at least m consecutive squares all containing the same symbol, the game ends and the winner is the player who placed the last symbol. When all the squares of the grid are filled, if neither player has won, the game ends in a draw.

Your task is to analyze the state of a Tic Tac Toe board, and determine whether the game is still in progress, or if it has completed, who won, or if the game ended in a draw. You should also detect erroneous states of the Tic Tac Toe board that could never occur during an actual game.

Input

The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains the two integers n and m, separated by spaces, with 1 <= m <= n <= 1000. The following n lines of the test case each contain one row of the Tic Tac Toe board. Each of these lines contains exactly n characters, and each of these characters is either an X, an O, or a period (.), indicating an empty square.

Output

For each test case, output a single line containing the appropriate string X WINS, O WINS, or DRAW if the game is over, the string IN PROGRESS if the game has not yet finished, or ERROR if the state of the board could never occur during a game.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Finding the convex hull of a set of points is an important problem that is often part of a larger problem. There are many algorithms for finding the convex hull. Since problems involving the convex hull sometimes appear in the ACM World Finals, it is a good idea for contestants to know some of these algorithms.

Finding the convex hull of a set of points in the plane can be divided into two sub-tasks. First, given a set of points, find a subset of those points that, when joined with line segments, form a convex polygon that encloses all of the original points. Second, output the points of the convex hull in order, walking counter-clockwise around the polygon. In this problem, the first sub-task has already been done for you, and your program should complete the second sub-task. That is, given the points that are known to lie on the convex hull, output them in order walking counter-clockwise around the hull.

Input

The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains a single integer 3 <= n <= 100000, the number of points. The following n lines of the test case each describe a point. Each of these lines contains two integers and either a Y or an N, separated by spaces. The two integers specify the x- and y-coordinates of the point. A Y indicates that the point is on the convex hull of all the points, and a N indicates that it is not. The x- and y-coordinates of each point will be no less than -1000000000 and no greater than 1000000000. No point will appear more than once in the same test case. The points in a test case will never all lie on a line.

Output

For each test case, generate the following output. First, output a line containing a single integer m, the number of points on the convex hull. Next output m lines, each describing a point on the convex hull, in counter-clockwise order around the hull. Each of these lines should contain the x-coordinate of the point, followed by a space, followed by the y-coordinate of the point. Start with the point on the hull whose x-coordinate is minimal. If there are multiple such points, start with the one whose y-coordinate is minimal.

Sample Input  Download

Sample Output  Download

Tags

Discuss