Description

A binary search tree is a binary tree with root k such that any node v in the left subtree of k has label (v) <label (k) and any node w in the right subtree of k has label (w) > label (k).

When using binary search trees, one can easily look for a node with a given label x: After we compare x to the label of the root, either we found the node we seek or we know which subtree it is in. For most binary search trees the average time to find one of its n nodes in this way is O(log n).

Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?

Input

The input will contain a number 1 <= i <= 1000 per line representing the number of elements of the set.

Output

You have to print a line in the output for each entry with the answer mod 32767 to the previous question.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  Alexander was a strict king. He asked the army not only had to win but defeat the enemy in the way he wanted. Because of stern discipline, the force he had was fighting and winning repeatedly.

  One of training was marching on a grid map. The army was on the northwestern square at first, and he gave some orders to the army. They would move into the southeastern square in the end. Alexander only gave them two types of orders: go east or go south. Then they would move along the direction to the next adjacent square on the map. Since Alexander would boil over when they made any mistake and probably killed somebody, they moved as Alexander’s commands in order to survive.

  However, the map was not safe since an ancient wizard set magic traps in some squares. Once the army moved into the trap, all of them would be wiped out. As a wisdom king, Alexander knew which square was not safe so that the force could pass the map without any casualty. You, as a loyal retainer, were asked to count the number of ways to pass through the map.

Input

   The first line is an integer T followed by T test cases. Each case will start with two integers N and M represented the number of row and column in a map. The next line is an integer K followed by K positions (r_i, c_i) in next K lines contained traps on the map.

   T < 20 and 1 < N, M < 18

   Notice that the first sample input is corresponding to the example above.

Output

   For every case, output the case number and the number of way to pass through the map. See sample output for more details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

“How am I ever going to solve this problem?” said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?

Your program has to be efficient!

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output consists of one integer representing the largest number of points that all lie on one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Institute of Bioinformatics and Medicine (IBM) of your country has been studying the DNA sequences of several organisms, including the human one. Before analyzing the DNA of an organism, the investigators must extract the DNA from the cells of the organism and decode it with a process called ``sequencing''.


A technique used to decode a DNA sequence is the ``shotgun sequencing''. This technique is a method applied to decode long DNA strands by cutting randomly many copies of the same strand to generate smaller fragments, which are sequenced reading the DNA bases (A, C, G and T) with a special machine, and re-assembled together using a special algorithm to build the entire sequence.


Normally, a DNA strand has many segments that repeat two or more times over the sequence (these segments are called ``repetitions''). The repetitions are not completely identified by the shotgun method because the re-assembling process is not able to differentiate two identical fragments that are substrings of two distinct repetitions.


The scientists of the institute decoded successfully the DNA sequences of numerous bacterias from the same family, with other method of sequencing (much more expensive than the shotgun process) that avoids the problem of repetitions. The biologists wonder if it was a waste of money the application of the other method because they believe there is not any large repeated fragment in the DNA of the bacterias of the family studied.


The biologists contacted you to write a program that, given a DNA strand, finds the largest substring that is repeated two or more times in the sequence.

Input

The first line of the input contains an integer T specifying the number of test cases ( 1 <= T <= 100 ). Each test case consists of a single line of text that represents a DNA sequence S of length n ( 1 <= n <= 1000 ).


You can suppose that each sequence S only contains the letters A, C, G and T.

Output

For each sequence in the input, print a single line specifying the largest substring of S that appears two or more times repeated in S , followed by a space, and the number of ocurrences of the substring in S .


If there are two or more substrings of maximal length that are repeated, you must choose the least according to the lexicographic order.


If there is no repetition in S , print ``No repetitions found!''

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a square area with edge length N. The lower left corner is (0, 0) and the upper right corner is (N, N). There is one person stand on each point (x, y). (0 ≤ x, y ≤ N) x and y are integers. Suppose you are the one at (0, 0), please calculate the number of people you can see directly. For example, the edge length of the sqaure is 2. You can see (0, 1), (1, 0), (1, 2), (2, 1) and (1, 1) directly.

Input

There are multiple test cases. The first line contains an integer T (T ≤ 100) which represents the number of test case. The next T lines, each line contains an interger N (0 < N ≤ 1000000), which represents the length of the square.

Output

Please output the number of people for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss