Description

Problem A - The Problems

HT is drawing up the upcoming midterm. In order to get more ideas, HT asks his TA to prepare n distinct problems. Each problem will be inspected carefully and be graded by its quality, said to be a_i. HT wants to find out how many different kinds of "quality score" are there in the problem set that TA gave to him.

Input

The first line contains an integer n, representing the number of problems TA give to HT.

The second line contains n integers a_i, representing the quality score of each question.

It is guaranteed that :

• testcase #1 : Sample Input
• testcase #2~3 : 1 ≤ n ≤ 100, 1 ≤ a_i ≤ 3
• testcase #4~6 : 1 ≤ n ≤ 100, 1 ≤ a_i ≤ 100
• testcase #7~9 : 1 ≤ n ≤ 100, -100 ≤ a_i ≤ 100
• testcase #10 : 1 ≤ n ≤ 2*10⁵, -10⁵ ≤ a_i ≤ 10⁵

If you can't pass testcase #10 immediately, try to solve another two problems first. 

Output

Please output a line represents the number of different kinds of "quality score" in the problem set.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem B - Sticks

After inspecting the problem set TA give to HT, he feels a little tired and decides to go for a walk. As a naughty boy, HT picks up n sticks during his walk, each with a length a_i. HT wonders if he can choose three from the n sticks such that the three sticks can form a triangle with the maximum possible perimeter (周長). HT is a busy professor, so he wants you to help him decide the maximum possible perimeter of the triangles that could be formed.

Input

The first line contains an integer T, representing the number of testcases.

Each testcase contains two lines :

The first line contains an integer n, representing the number of sticks HT picks.

The second line contains n integer a_i, representing the length of each sticks.

It is guaranteed that :

• testcase #1 : Sample Input
• testcase #2~4 : T = 1, n = 3, 1 ≤ a_i ≤ 100
• testcase #5~8 : 1 ≤ T ≤ 10, 1 ≤ n ≤ 100, 1 ≤ a_i ≤ 100
• testcase #9~10 : 1 ≤ T ≤ 10, 1 ≤ n ≤ 1000, 1 ≤ a_i ≤ 100

If you can't pass testcase #9 & #10 immediately, try to solve another two problems first.  

Output

For each testcase, please output a line contains one integer represents the length of the triangle with the maximum possible perimeter. If the sticks can't form a triangle, please output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem C - Lucky Substrings

HT Chen is happy that you guys have solved the "exquisite substrings" problem! In order to improve your programming ability, here comes the next challenge :

HT's lucky number is 9. For a string s consists of digits ranged from '0' to '9', if s contains at least one digit of lucky number 9, then s is called "lucky string". HT wants to know how lucky he is today. As a kind of divination, HT will randomly write down a list of strings and ask you to calculate the number of "lucky substrings" in each string.

(If naughty HT is very unlucky today, maybe the midterm will become harder than usual.)

Input

There are multiple lines in each testcase. Each line contains a string s_i that HT writes on the paper.

The input file is ended by 'EOF'.

It is guaranteed that :

• At most 10 lines in each testcase.
• testcase #1 : Sample Input
• testcase #2~4 : 1 ≤ | s_i | ≤ 10, at most one "lucky number" appears in each line
• testcase #5~8 : 1 ≤ | s_i | ≤ 100
• testcase #9 : 1 ≤ | s_i | ≤ 5000
• testcase #10 : 1 ≤ | s_i | ≤ 200000

If you can't pass testcase #9 & #10 immediately, try to solve another two problems first. 

Output

For each string s_i, please output a line contains one integer representing the number of "lucky substrings" in s_i.

Sample Input  Download

Sample Output  Download

Tags

Discuss