Description

My Legend is a facebook game developed by Happy Elements. It is a RPG game. You are the hero in that world, you will kill enemies and get items, money and experience points. You can level up and get higher ability points by accumulating of the experience points. You can also use the items dropped from the enemies to make better equipment. The money can buy items and upgrade the buildings. There is also a gem system. You can add the gems on your equipment to make them stronger.

This time a new update version is coming. You will get a sequence of items, and there will be some rules told you that if two kinds of the items are adjacent, they can become a new item. This new item could be the same with one of the original item. And each fusion will cost some money. Now given you the sequence of the items, you want to use the minimum cost to make the sequences of items in to only one item left. Please write a program to calculate the minimum cost.

For example, you get "ANT" "BEAR" "CAT" "CAT" this four items. And the following are the rules of fusion.

(a) ANT BEAR CAT 10
(b) CAT CAT CAT 15

The first rule means if "ANT" and "BEAR" are adjacent(no matter which one is on the left), they can become "CAT" using 10 dollars, and in this case, you want to make "CAT".

So a possible step will be

1. using rule (a) and pay 10 dollars to make the sequence become "CAT" "CAT" "CAT".
2. and using rule(b) two times with paying 15+15 dollars and you will get the goal.

The total cost of this case is 40.

Input

The first line of the input is an integer Z (1 ≤ Z ≤ 30), which means the number of test cases below.

The first line of each test case contains two integers N and M, where N is the length of the given sequence and M is the number of rules (1 ≤ N ≤ 50, 1 ≤ M ≤ K(K-1)/2).The following N lines describe the sequence. Each line contains a string represent the item's name. The length of the items' name are smaller than 10 and contains only capital English letters. And there are at most K kinds of items. (1 ≤ K ≤ 10) The following M lines describe the rules. Each line contains three strings and a integer V (1 ≤ V ≤ 10⁵). It means if the first two kinds of item are adjacent, the can become the third item by using V dollars. The next line of the input is the kind of the item you want to get.

Output

For each test case, print an integer on a line which means the minimum number of dollars you need to pay to make the item you want. If there is no way to make the item you want, please print "IMPOSSIBLE" (without quote) on the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Benson, the manager of the park, is trying to assign the jobs to his workers. There are N workers and N different kinds of jobs. Each of the workers is able to, with various length of time required, finish a few kinds of jobs, but each of them must concentrate on finishing a single job and should not help with other jobs even if her or his own job is done.

They all start their work right after the jobs are assigned, so the time to call it a day depends on the latest ones who finish their jobs. The manager, and of course all of the workers, wish to go home as early as possible, so please help him to figure out a way to assign the jobs, with the restriction that each job is done by exactly one person and each person works on exactly one job, such that the latest finished job can be done as early as possible.

Input

The first line of the input is an integer Z (Z ≤ 10), which means the number of test cases that follows.

For each test case, the first line contains an integer N (N ≤ 100), which is the number of workers and jobs. Each of the next N lines contains N integers, where the j-th integer on the i-th line is the number of units of time for the i-th worker to finish the j-th kind of job, or -1 if the i-th worker should never work on the j-th kind of job. It is guaranteed that there is at least one possible assignment for each test case in the input.

There will be a leading blank line for each test case in the input.

Output

For each test case, output a line containing the test case number (starting from 1) and an integer, which is the minimum number of units of time to call it a day. The detailed format is shown in the sample output, and note that there is a single space character before the sharp sign and after the colon.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a duplicated maps like the ones shown below, you have to try to move ‘A’ and ‘B’ from the initial cell to the goal cell ‘E’ simultaneously. In these maps, you may travel through those free cell ‘.’, and may not move to the blocked cell ‘#’.

####### #######
#.....# #.....#
#.....# #.....#
#..E..# #..E..#
#.A...# #.B...#
#.....# #.....#
####### #######

However, there is a restriction that, whenever you try to move ‘A’ or ‘B’ a step to one of the adjacent cells in four directions, right, left, up and down, the other one must passively move a step to the adjacent cell in the opposite direction if possible. For example, if you move ‘A’ one step left, then ‘B’ must move one step right if the right cell is not a blocked cell. The following maps are the results after you move ‘A’ two steps up from the original position in the maps above.

####### #######
#.....# #.....#
#.A...# #.....#
#..E..# #..E..#
#.....# #.....#
#.....# #.B...#
####### #######

Note that in the second step, the cell that ‘B’ forced to move in is a blocked cell, so ‘B’ remains in the same position after ‘A’ moves up.

You have to find out the minimum number of steps to move ‘A’ and ‘B’ to the goal cell simultaneously, which means that ‘A’ and ‘B’ stay in the goal cell after a sequence of move. Note that moving one of them a step and forced the other one to move a step in the opposite direction is considered as a single step, instead of two. The starting cell and the goal cell are always considered as a free cell.

Input

The first line of the input is an integer Z (Z ≤ 10), which means the number of test cases that follows.

For each test case, the first line contains two integers N and M (1 ≤ N, M ≤ 20), denoting the number of rows and columns of the maze. Each of the following N lines contains M characters representing the cells. The character ‘.’ means a free cell, ‘#’ means a blocked cell, ‘S’ means the starting cell of ‘A’ and ‘B’, and ‘E’ means the goal cell. There will be exactly one ‘S’ and ‘E’ in the maze, and you may safely assumed that the maze will be surrounded by the blocked cells.

There will be a leading blank line for each test case in the input.

Output

For each test case, output a line containing the test case number (starting from 1) and the minimum number of steps to move ‘A’ and ‘B’ to the goal cell simultaneously. Output an integer -1 if it is impossible to achieve the goal. The detailed format is shown in the sample output, and note that there is a single space character before the sharp sign and after the colon.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, you are playing a game called “Simple Number” with CKL.

The rules of the game is following:

At first, the judge decides a positive integer R to be the range.
Then, CKL will start the game. The two players try to find a special integer N in turns.
The special integer N is a positive integer less than R.
N is co-prime with R. (that is, gcd⁡(N, R) = 1)
The player who cannot find the new N will lose the game.

For example, if the judge decides R is 8, then one of the game’s situations will be:

• Turn 1: CKL chose 1.
• Turn 2: You chose 7.
• Turn 3: CKL chose 5.
• Turn 4: You chose 3.
• CKL loses!!!!!!

But you are a lazy person. You don’t want to play too many turns. Just want to know how many turns will be played under the range R. Please write a program to solve it.

Input

The first line of the input is an integer Z (Z ≤ 10⁵), which means the number of test cases.
For each test case, one line contains one positive integer R (R ≤ 10⁹).

Output

For each test case, output the test case number and the turns of the game under the range R.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are a H(Heuristic)-Game lover. One day, you find out that a new H-Game is selling now. But the limit edition of this game is only sold in a city. You will ride your bicycle to the city to get it, but unfortunately, your energy is also limited. You can't ride the bicycle more than K kilometers in one day. You should take a rest in some city and go out on the next day. You want to buy the H-Game as soon as possible. Please calculate that after at least how many days you can get to the city which the H-Game is sold.

Input

The first line of the input is an integer Z (1 ≤ Z ≤ 30), which means the number of datasets below. The first line of a dataset contains two integers N and M, where N is the number of the cities and M is the number of roads which connect the two cities. (1 ≤ N ≤ 100, 1 ≤ M ≤ N(N-1)/2) The cities are numbered from 1 to N. The following M lines describe the roads. There are three integers a, b and c on one line. Which means there exist a road from city a to city b and the length of it is c kilometers. The roads are bi-connected. The next line contains three integers S, E and K (1 ≤ K ≤ 10⁹). S means the city you live, E means the city where you can get the H-Game and K means the maximum distance you can ride in one day.

Output

For each dataset, please print an integer which is number of the minimum day you can get the H-Game. If you can reach to the city, please print "IMPOSSIBLE"(without quote) on the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

People lost their jobs during the great depression. In that time, people didn’t care about anything except power and money. They also used both to control another one. If some one's power and money are both less than yours, then you can control him. We have some data of many people. For every one, please compute how many people he can control.

Input

The first line of the input is an integer Z (Z ≤ 10), which means the number of test cases.
For each test case, one line contains one positive integer N (N ≤ 10⁵).
There are N lines following. For each line, there are two integers P_i, M_i (|P_i|, |M_i| ≤ 10⁶).

Output

For each test case, output the test case number in the first line, and then N lines follows.

Every line contains one integer representing the number of the people the person can control. Output one blank line between every two test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

My Kingdom is a facebook game which is developed by Happy Elements. In this game, you help the king to develop the kingdom. You can grow crops, train the army, build shops and get money and etc. There are also some mini games, such as BrickBreaker. You can get money or items in the mini game.This time a new update version is coming. They add a mini game called "Mystery Shape". The shape pattern is like the picture below.

You need to put as much as you can on a given plate to earn more award. The pattern can be rotated and flipped. For example, given the 5 x 5 plate below and the place with X is the forbidden area. In this case you can put at most 3 pieces of this pattern.

Input

The first line of the input is an integer Z (1 ≤ Z ≤ 30), which means the number of test cases below. The first line of a test case contains two integers N and M, where N is the height of the plate and M is the width of the plate (3 ≤ N ≤ 7, 3 ≤ M ≤ 7). The following N lines describe the plate. Each line contains M characters. The character '.' means it is an empty area, you can put the shape on it. And the character 'X' means it is an forbidden area, you can't put the pattern on it.

Output

For each test case, print an integer on a line which means the maximum number of pieces of the pattern you can put on the plate.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In computational mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems.

In programming contests, we usually use one of the two following forms of Catalan Number:

1. Division Version:

2. Non-division Version:

It's useful in many problem. There are some examples:

● The number of containing n pairs of parentheses which correct matched:
For n = 3, C(3) = 5:
((()))
()(())
()()()
(())()
(()())

● The number of full binary trees with n + 1 leaves
For n = 3, C(3) = 5:

● The number of different ways a convex polygon with n+2 sides can be cut into triangles by connecting vertices with straight lines.
For n = 4, C(4) = 14:

Input

The first line of the input is an integer Z (Z ≤ 500), which means the number of test cases. For each test case, one line contains one non-negative integer N (N ≤ 500). It is guaranteed that the number of digits of the largest Catalan number in this problem is less than 300.

Output

For each test case, output the test case number and the N-th Catalan number.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Image a two dimensional grid. Starting from the origin (0, 0), you have to find out how many ways to move back to the origin after K steps. In each step, you may move to those adjacent points in four directions, right, left, up, down, and you may visit the points more than one times during a walk. Two walks are considered different if not all of the points they visit in each step are the same.

Input

The first line of the input is an integer Z (Z ≤ 10), denoting the number of test cases that follows.

Each test case contains only a single integer, which is the number K (K ≤ 20) defined in the problem description.

There will be a leading blank line for each test case in the input.

Output

For each test case, output a line containing the test case number (starting from 1) and number of possible walks. The detailed format is shown in the sample output, and note that there is a single space character before the sharp sign and after the colon.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In an infinite binary tree:

• In an infinite binary tree:
• If a node is labeled with the integer X, then its left child is labeled 2X and its right child 2X+1.
• The root of the tree is labeled 1.

A walk on the binary tree starts in the root. Each step in the walk is either a jump onto the left child, onto the right child, or pause for rest (stay in the same node). A walk is described with a string of letters 'L', 'R' and 'P':

• 'L' represents a jump to the left child;
• 'R' represents a jump to the right child;
• 'P' represents a pause.

The value of the walk is the label of the node we end up on. For example, the value of the walk LR is 5, while the value of the walk RPP is 3.

A set of walks is described by a string of characters 'L', 'R', 'P' and '*'. Each '*' can be any of the three moves; the set of walks contains all walks matching the pattern.

For example, the set L*R contains the walks LLR, LRR and LPR. The set ** contains the walks LL, LR, LP, RL, RR, RP, PL, PR and PP.

Finally, the value of a set of walks is the sum of values of all walks in the set. Calculate the value of the given set of walks.

Input

The first line of the input is an integer Z (1 <= Z <= 15), which means the number of test cases. For each test case, one line containing a string describing the set. Only characters 'L', 'R', 'P' and '*' will appear and there will be at most 10000 of them.

Output

For each test case, output the test case number and the value of the set.

Sample Input  Download

Sample Output  Download

Tags

Discuss