Description

After Knuckles escaped from the dungeon he faced on another difficulty. He meet an elder who claimed that he knew where to find the queen. As long as Knuckles solve the question.

---

The elder will give Knuckles n integers, and Knuckles can make a big integer by appending those integers after one another. 

 

For example:

If n = 3, Knuckles have three integers: "71", "87", "22". Following integers can be made:

"718722", "227187", "877122", "228771".......

In this example, 6 such integers can be made. Knuckles  need to find the biggest integer.  In this example, the answer will be "877122".

 

Help Knuckles find the biggest integer he can make.

 

Input

 

The input will end by EOF.

Each input contains several lines.

First line contains an integer n(1 <= n <= 100).

The following n lines, each line contains an interger a_i(1 <= a_i <=10⁹⁹⁹)

Each testcase contains at most 10 input.

 

Output

 

For each input, print the biggest integer you can make

remember to print \n after each output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After some hard work of finding his queen, Knuckles finally arrived NTHU!

Knuckles is exhausted. He wants to grab some delicious food. However, as all of us know......

THERE IS NO "DELICIOUS" FOOD IN HSINCHU.

(Actually there are some restaurants that are not bad. But just "not bad"...)

 

 

This truth, which is cruel, hits Knuckles pretty hard. Knuckles doesn't give up and start his journey of finding delicious food in Hsinchu. 

However, the more he goes out and seeks, the truth is just getting more clear...

The i-th time that those bad-taste restaurants Knuckles found is F_i . Knuckles found that F₁ = 1, F₂ = 1, and F_i = F_i-1 + F_i-2 .

The more Knuckles goes out, the more bad-taste restaurants he found.

He is tired of finding more and more bad restaurants. He just wants to know there are how many bad restaurants when he goes out for the i-th time.

---

• There's a sequence F.
• F₁ = 1, F₂ = 1, F_i = F_i-1 + F_i-2.
• Find out F_i .

Hint：

Input

The input contains multiple lines, ended by EOF.

Every line contains an integer i.

1 <= i <= 10¹⁸.

There will be at most 20 lines.

Output

Output F_i.

Because F_i might be too big, the answer should mod 10⁹+7, which means you should output F_i % (10⁹+7).

Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I shall take no wife, hold no lands, father no children.

~ by anonymous loser.

The night's watch needs to guard The Wall.

But they're lack of resource. They can only choose q-2 men from q men to guard The Wall.

Help them find the maximum number of section they can protect.

There're n sections in a line numbered from 1 to n.

There're q soldiers, for i-th soldier, he can guard from section L_i to R_i(1 <= i <= q)

A section is guarded if at least one soldier guard the section.

You can only hire q-2 soldiers.

You need to find the maximum number of sections that can be guarded by hiring q-2 soldiers from q soldiers.

 

Example

If you got n = 4 sections and q = 3 soldiers.

First soldier guard L_1 = 1, R_1 = 1.

Second soldier guard L_2 = 2, R_2 = 2.

Third soldier guard L_3 = 3, R_3 = 4.

You can hire q-2 = 1 soldier.

The best solution is hired the third soldier then you got 2 section guarded.

The answer will be 2.

Input

The input first contains one integer t( 1 <= t <= 5) which means the number of testcases.

Each testcase first contains two numbers n, q(3 <= n, q <= 5000).

Then the following q lines, each line contains two integer L_i, R_i( 1<= L_i <= R_i <= n )

Output

For each testcase print a integer which means the maximum number of sections that can be guarded by hiring q-2 soldiers.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Help! Help! We're all gonna be flunked by these devil-like TAs!

── Students

It's said that there's a course that every student who take that course will be flunked...

The course might be Advanced Calculus, Complex Analysis ... it could be Introduction to Programming! Who knows?

The only thing you know is that the professor of this course is Professor Chen-Tzong Hwann(煥陳宗), a.k.a. CTH. His TAs keep producing extremely hard problems, leads that every student are going to be flunked.

However, flunking every student means that CTH needs to submit a report to the administration of the university, and CTH is too lazy to write that report, so he decide to let exactly one student pass.

---

The class have $n$ students, CTH will organize a tournament. The tournament is going to be held with the following format:

1. If there's only one student remaining, then the student is the winner, the tournament ends.

2. If the number of remaining students is even, they split in pairs and compete for each pair. The loser of each pair will be eliminated(no draws for this competition).

3. Otherwise, if the number of remaining students is odd, they'll compete each other once in round robin tournament and decide the final winner, then the tournament ends.

   • For the round robin tournament part, if there are $x$ students remaining, there will be $\frac{x(x-1)}2$ competitions since they compete with everyone once.

For example, if there are 20 students initially, they would have 10 competitions, then 10 students are eliminated. The remaining 10 students would have 5 competitions and remain 5 students, then have 10 competitions for round robin tournament. Totally there are 10+5+10=25 competitions.

CTH's TA want to see exactly $n$ competitions in order to see them suffer. He asks you to calculate the minimum number of students that the course need to have.

---

Hint:

This problem involves brute force(暴力搜尋) and binary search(二分搜尋). One of the solutions is to combine the two techniques. You may try to think what we can enumerate, and what we can do a binary search.

Brute Force: usually applied when the number is small.

Binary Search: If the sequence is in increasing / decreasing order, the binary search technique can be applied.

Input

The first line contains an integer $T$. There are $T$ testcases below. $1\le T\le 64$.

There are $T$ lines below. Each line contains exactly one integer $n$, the number of competitions.

$1\le n\le 10^{18}$.

Output

For each testcase, output its minimum number of students that the course need to have with newline.

If there's no such answer, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Do you know de way?

by uganda knuckles

 

Knuckles are magical animals and I don't know how to descripe such non-sense

google it yourself :) 

Two string belongs to same group if :

1. there exists a character that exist in both string.

2. there exists a character in both string A and B,

   and there exists another character in both string B and C,

   then A, B, C belong to same group.

 

Now, given n strings, you need to answer how many groups are there?

A group can have members from 1 to n.

 

 

Example:

Given n=4

strings are "a", "b", "ab", "d".

"a" and "ab" and "b" belong to same group.

"d" form a group by it self.

Therefore there are 2 groups.

Hint:

Your first thought might be that if there exist a character in both string you can create an edge between both string .

Then you can use DFS to find out how many connected components(連通塊) are in the graph.

 

It's similar to 12155 - Cat-Toast Crisis .

But in this problem, this way will cause TLE.

You need to change the way you construct the graph, 

you can't just easily connect two string, think another way (:

 

Input

First line contains only one integer t( 1<= t <= 30) which means the number of testcases.

In each testcase:

First line contains one integer n( 1 <= n <= 2000 ).

And the following n lines, each line contains one string( 1 <= length of string <= 1000 )

Output

For each testcase output the number of groups.

Remember to print '\n' at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss