ACM International Collegiate Programming Contest, Tishreen Collegiate Programming Contest (2017)
A. Printing Books
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Nour likes comic books so much that she decided to write her own comic book. Once she had this amazing idea, she started working on it immediately.

After a few days she finished her very first comic book. Since Nour is a workaholic, she wrote a huge comic book during these days with a lot of pages. Since Nour likes to be special in everything she started numbering her comic book from number X. In other words the first page has number X written on it, the second page has number X + 1 written on it, and so on.

Like we all know, Nour enjoys giving her friend Ahmed a hard time. That's why one day on their way to work, she asked her friend Ahmed the following question:

"Say Ahmed, can you guess the number of pages of my new comic book? I used a total number of digits equal to N, and started numbering my comic book from the number X, or say that such a thing is impossible. Since you are only an experimental physicist I'll give you an example: the number 99 has 2 digits on it. So if I wrote only 2 pages starting from the number 99, I would have used 5 digits to number my comic book".

Ahmed is so busy driving, and also he is really holding his nerves not to throw Nour out of the window right now. So he turned to you to help him solve this idiotic question from his annoying friend.

Input

The first line contains an integer T, the number of test cases.

Each line of the following T lines describes a single test case. Each test case contains 2 space separated integers N, X (1 ≤ N, X ≤ 1015).

Output

For each test case print a single line, containing a single integer, denoting the number of pages in Nour's comic book, or print -1 if such a thing is impossible.

Example
Input
2
11 5
12 5
Output
8
-1

B. Ali and Wi-Fi
time limit per test
6 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Ali lives in a very crowded city and a very large apartment. His apartment looks like an almost infinite 2D plane. In this city almost all his neighbors have WiFi networks, except for him. Precisely, from his apartment his laptop can receive N WiFi networks.

One day Ali wrote a program that can hack his neighbors' WiFi networks. Furthermore, he learned how to stand in a point, hack almost all the WiFi networks that reaches that point, and join them in one ultra-speed network.

Each WiFi network is described as a circle with its center on the point (x, y), a radius equal to R and a network speed equal to S.

However, Ali's program can join at most M networks. When Ali's program joins many networks, the resulting network will have the total sum for speeds of all networks.

Ali wants to choose a point at his apartment that will get him the maximum total speed of WiFi networks. Can you help him calculate the maximum total WiFi network speed he can get if he chooses his location optimally?

Input

The first line contains an integer T, the number of test cases.

The first line of each test contains (1 ≤ N ≤ 100) the number of WiFi networks and (1 ≤ M ≤ 100) the maximum number of networks Ali can join.

The following N line contains the description of N WiFi networks. The center coordinates (0 ≤ x, y ≤ 103) , the radius (1 ≤ R ≤ 103) and the network speed (0 ≤ S ≤ 106) .

Output

For each test case print a single line, containing a single integer, denoting the maximum total WiFi network speed Ali can get, if he chooses his location optimally.

Example
Input
1
3 2
0 0 2 5
4 0 1 10
2 2 4 2
Output
12

C. Shahhoud Training Hussain
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Ever since coach Shahhoud started the series "Problem Every Day" . Hussain decided to train really hard. After all, he may get a chance to qualify for the upcoming SCPC contest !

Shahhoud gives Hussain K problems everyday. However, Hussain can solve at most P problems everyday.

At the end of the Nth day of training, Shahhoud wants to know how many problems did Hussain miss and hasn't solved yet?

Input

The first line contains an integer T, the number of test cases.

Each line of the following T lines describes a single test case. Each test case contains 3 space separated integers K, P, N (1 ≤ K, P, N ≤ 109).

Output

For each test case print a single line, containing a single integer, denoting the number of problems Hussain has missed by the end of the Nth day.

Example
Input
3
2 1 3
4 1 10
3 2 1
Output
3
30
1

D. Largest Group
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

One day your university decided to run some statistics. They wanted to study friendship relations among boys and girls, and its effectiveness on their grades.

Strange thing about your university is that it has the exact same number of boys and girls. More formally, the university has P boys numbered from 1 to P, and P girls numbered from 1 to P.

We know that any pair of boys are surely friends, and any pair of girls are definitely friends. However, boys and girls are not always friends. To be precise, the university has a list of length N containing the friendship relations between girls and boys. the ith friendship relation is described by two integers bi and gi meaning that the boy number bi and girl number gi are friends.

One of the statistics your university is interested in, is the largest group of people (boys and girls) where any pair of them are friends. Can you write a program that would solve such a problem?

Input

The first line contains an integer T, the number of test cases.

Each test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P2).

N lines follow. The ith line of them contains 2 space separated integers bi, gi describing a friendship relation.

Output

For each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends.

Example
Input
2
4 5
1 2
2 2
3 2
4 2
1 4
3 4
1 2
2 1
1 1
2 2
Output
5
4

E. Minesweeper
time limit per test
15 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Have you ever played Minesweeper? It’s a cute little game that originates from the 1960s, and has been written for many computing platforms in use today.

The game consists of a two dimensional grid, and there are two types of cells in it.

A mined cell, and an empty cell, which contains a single digit that indicates how many adjacent cells contain mines. Eech cell has at most 8 adjacent cells.

In this version of the game, you are going to build a level with the following rules:

  • Every mined cell has to be a neighbor of at least one empty cell.

  • Every empty cell can have at most M adjacent mines.

For instance, the following is 4 * 5 valid grid with 12 mines (which are represented by an '*' character) and the maximum number for the empty cells is M = 3 :

3 * * 3 1

* * * * 2

* * * * 2

3 * * 3 1

We are interested in the maximum number of mines that a grid with those properties can contain, can you find the answer for us?

Input

The first line contains a single integer T denoting the number of test cases.

Each test case consists of one line which contains three space separated integers:

The number of the rows in the grid r. (2 ≤ r ≤ 6).

The number of the columns in the grid c. (2 ≤ c ≤ 6).

The maximum number that any empty cell can contain. (1 ≤ M ≤ 8).

Output

For each test print one line containing one integer, the maximum number of mines that a grid can contain.

Example
Input
2
4 5 3
3 3 4
Output
12
6
Note

The grid in the statement is a valid grid for the first sample.

F. A Missing Problem in TCPC2017
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

While the judges of TCPC were busy preparing the problems, they encountered a strange problem. One of the problems was missing !!

The judges remember that they prepared exactly N problems and that they were numbered from 1 to N. They also remembered that the problems were sorted according to their number.

The judges started investigating but they realized that they don't have enough time, so they asked the contestants for help.

Input

The first line contains a single integer T, the number of test cases.

The first line of each test case consists of a single integer N (2 ≤ N ≤ 12), denoting the number of problems.

The second line of each test case contains N - 1 space separated integer denoting the number of each problem the judges didn't miss. Yet!

it's guaranteed that the numbers are given in the increasing order.

Output

For each test case print a single line, containing a single integer, denoting the number of the missing problem.

Example
Input
1
4
1 2 4
Output
3

G. Robots
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Robotics Olympiad teams were competing in a contest.

There was a tree drawn on the floor, consisting of n nodes and n - 1 edges. The nodes are numbered from 1 to n, and each edge has a weight. The tree is rooted at the first node. q teams are participating, and each team is given an integer xi. Their robot should start at node 1, and move in the following way until there are no valid moves left: From all the edges between the current node and it's children, go through the edge with the maximum value less than xi. Note that the robot can't move to the parent, only to children.

However, the teams weren't able to program the robots to return to them after the contest, so they had to manually pick them up. Since the tree can be quite large, they need your help to determine where each robot ended it's movement.

Input

The first line contains a single integer T, the number of test cases.

The first line of each test case contains two space-separated integers n and q. (1 ≤ n, q ≤ 105).

The following n - 1 lines contain 3 integers ui, vi, wi. This means that there is an edge connecting nodes ui and vi, with weight wi. (1 ≤ ui, vi ≤ n) (1 ≤ wi ≤ 109). It's guaranteed that all wi are distinct.

The following line contains q integers xi. (1 ≤ xi ≤ 109).

Output

For each test case, print one line with a single number Si, the sum of numbers of nodes where each robot ends.

Example
Input
1
5 7
1 2 3
1 3 4
3 4 9
3 5 7
1 3 4 9 8 7 10
Output
21
Note

In the sample test case, the robots end in the following nodes: {1, 1, 2, 5, 5, 3, 4}.

Si = 1+1+2+5+5+3+4 = 21.

Large I/O files. Please consider using fast input/output methods.

H. Buying Products
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Salim (a.k.a Slango) and his wife fight all the time. When Salim came home at night, his needy wife Afaf (a.k.a Afoufe) was waiting for him at the door.

"You don't buy any products for this house! You are a lousy husband! Well guess what?? You are not coming home before buying me exactly K products, or you are sleeping on the streets!!". Said his wife.

"I'm going to buy you these products, but when you open that door you are divorced by 3 you needy wife!!". Thought Salim to him self.

Anyway, having no other option, Salim went down the stairs and headed to the nearby mall. the mall has exactly N shops. Salim knows that each of these shops has exactly 3 products (it's sales time and shops are almost empty).

However, Salim knows that buying all the 3 products of some shop will cause the owner of the shop to ask him for a huge amount of money, because he will say that the last piece is very rare. Thus, he made a rule, he will buy at most 2 products from every shop.

Salim is really tired and he just wants to go home and sleep a while in order to wake up in the morning and divorce his needy wife. Also, Salim doesn't really care about the quality of the products, he just wants to buy them with the lowest possible price. Can you help him calculate the minimum amount of money he needs to spend in order to buy his wife exactly K products, while buying at most 2 products from any given shop?

Input

The first line contains an integer T, the number of test cases.

The first line of each test case contains 2 space separated integer N and K (1 ≤ N ≤ 1000)(1 ≤ K ≤ 2N).

N lines follows. The ith line contains exactly 3 space separated integers denoting the prices of the 3 products at the ith shop. (1 ≤ Pij ≤ 106)

Output

For each test case print a single line, containing a single integer, denoting the minimum price needed to buy exactly K products from the given shops while fulfilling the above given condition.

Example
Input
1
3 4
1 10 300
4 5 6
1 100 1
Output
7

I. A Movie in Byteland
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

There are two ways of reading names in Byteland. Either from left to right, or from right to left. For example, if a person called "mike" went to Byteland, the citizens might call him "mike" or "ekim".

Feras is the Casting Director for a new movie. There are N actors in Byteland, and he has to choose some of them to act in the new movie.

Feras knows that all of the actors are good, so he is only worried about what order he is going to use in the list of chosen actors.

An actor i would be disappointed if another actor j was listed before him, while actor i has a lexicographically smaller name in any of the two ways mentioned above. In other words, he will be disappointed if actor j was listed before actor i in the final list and siltr < sjltr or sirtl < sjrtl.

siltr is the name of actor i written from left to right.

sirtl is the name of actor j written from right to left.

Feras wants to choose the maximum number of actors possible such that there exists a way to order them so that none of them would be disappointed. In addition, he wants that in each pair of consecutive names on the list, exactly one of them contains the letter "m" . (His crush's name has too many letters "m" and he wants to remember her while producing the movie)

Input

The first line contains an integer T, the number of test cases.

The first line of each test contains the number of actors N. (1 ≤ N ≤ 105)

Then N lines follow, the ith line contains the name of the ith actor written from left to right, the name consists of lowercase english letters. (1 ≤ |si| ≤ 105). It's guaranteed that the sum of the lengths of all the names in each test case will not exceed 106

Output

For each test print one line containing one integer, the maximum possible number of actors Feras can choose while keeping him and all the chosen actors happy.

Example
Input
2
3
aaa
ama
aza
3
abcdef
bcmde
cd
Output
3
1
Note

Large I/O files. Please consider using fast input/output methods.

J. The Volcano Eruption
time limit per test
5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

"The volcano erupted!". Shouted Shahhoud, as he was attempting to wake Saeed up.

"You need to save Noor, he is trapped in the lab next to the volcano!". Shahhoud said.

You can picture the road between the base and the lab as a rectangle whose bottom left corner is at (0, 0) and top right corner is at (W, L). There are n holes filled with lava from the volcano. The ith hole is a circle whose center is at coordinates (xi, yi) and has a radius of ri. The holes may intersect to make larger holes.

Saeed Starts his mission at any point on the bottom side of the rectangle ( any point (0...W, 0)), and has to reach any point on the top side of the rectangle ( any point (0...W, L)), in order to save Noor.

None of the holes intersect with the bottom or the top sides of the rectangle ( the starting and finishing line).

Saeed can take special suits in his anti-lava backpack. Each special suit allows him to swim in one or more intersecting holes (once he goes out of the lava onto the street, he has to throw away the suit). Saeed must stay inside the street at all times. Please note that if two holes are touching each other by the border, then Saeed can't walk from between them without wearing a special suit.

What is the minimum number of suits Saeed has to take with him in order to reach the lab and save Noor?

Input

The first line contains a single integer T, the number of test cases. The first line of each test case contains 3 integers N,W, and L. The number of holes, the width, and the length of the rectangle. (1 ≤ N ≤ 1000) (1 ≤ W, L ≤ 109) Each of the following N lines contain 3 integers (0 ≤ xi ≤ W), (0 < yi < L), and (1 ≤ ri ≤ 109), the coordinates and radius of the ith hole. It's guaranteed that none of the holes intersect with the bottom or the top sides of the rectangle ( the starting and finishing line).

Output

For each test case, output a single line containing a single integer, the minimum number of suits Saeed must take with him to save Noor.

Example
Input
1
5 5 18
4 2 1
2 12 3
4 6 2
2 6 1
1 7 1
Output
2
Note

The figure below shows a possible solution for the sample.

K. Poor Ramzi
time limit per test
10 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Ramzi is in a lot of troubles nowadays and he has a weird habit. When he starts thinking about his troubles, he takes a pen and starts writing a sequence of zeros and ones. We really don't know why!.

One day, he got sick of thinking about his problems and tried to keep himself busy by playing with the sequence he wrote. He divided the sequence into consecutive ranges, then he wrote down a new sequence consisting of the sum of digits in each range.

Once he finished, he noticed something, the sequence was palindromic. He called it a sumindrome sequence.

A palindromic sequence is a sequence that reads the same backward as forward, such as {3, 5, 7, 5, 3}. Ramzi wants to know how lucky he is, so he is interested in the number of different ways of dividing the original sequence leading to a sumindrome sequence. Ramzi doesn't like huge numbers, so he wants the answer modulo (109 + 7).

Can you help him and give him the answer?

Input

The first line contains a single integer T denoting the number of test cases.

Each test case consists of one line which contains the original sequence of zeros and ones.

The length of every sequence is less than or equal to 50.

Output

For each test print one line containing one integer, the number of different ways to divide the original sequence leading to a sumindrome sequence modulo (109 + 7).

Example
Input
2
0110
1001
Output
4
8
Note

The ways of dividing the sequence in the second sample are:

(1001) -> 2

(1)(001) -> 1, 1

(100)(1) -> 1, 1

(10)(01) -> 1, 1

(1)(00)(1) -> 1, 0, 1

(1)(0)(01) -> 1, 0, 1

(10)(0)(1) -> 1, 0, 1

(1)(0)(0)(1) -> 1, 0, 0, 1

L. Eyb0ss
time limit per test
7 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

PinkGuy is a 5-star Popstar in America and Japan. Known for his songs about self-motivation , fighting against racism and poverty. 50 Percent of his albums profit goes to charity. He's working now on releasing his new album "eyb0ss". He promised his friend wheelz that he is going to finish this album , before wheelz gets his new car. However, he is still in college and doesn't have much time to focus on his studies. He recently got an assignment , and he needs you to do it for him.

Given a 2D array N * N.Each cell is denoted by 2 integers Cell(R, C). R denoting the number of its row. C denoting the number of its column. The rows are numbered from 1 to N from top to down. The columns are numbered form 1 to N left to right.

Consider every sub-rectangle of this array. Each rectangle is identified by 2 cells Rectangle({R1, C1}, {R2, C2}) . {R1, C1} denoting its upper-left corner , {R2, C2} denoting its lower-right corner. A single cell is considered a rectangle.

You are asked to calculate the following sum :

MAX(R1, C1, R2, C2) is a function returns the maximum integer in the Rectangle ({R1, C1}, {R2, C2}).

MIN(R1, C1, R2, C2) is a function returns the minimum integer in the Rectangle ({R1, C1}, {R2, C2}).

Input

The first line contains a single integer T, the number of test cases. The first line of each test case contains a single integer N. (1 ≤ N ≤ 500). The following N lines each contains N integers, the values of the ith row of the array. Array values are between 1 and 500.

Output

For each test case, print one line containing one integer, the answer to the problem.

Example
Input
3
2
1 3
5 10
3
1 1 1
1 1 1
1 1 1
3
1 8 1
2 4 9
2 4 5
Output
27
0
131
Note

Large I/O files. Please consider using fast input/output methods.