Problem Statement

In AtCoder, a user's rating is given as a positive integer, and based on this value, a certain number of ^ is displayed. Specifically, when the rating is between 1 and 399, inclusive, the display rules are as follows:

• When the rating is between 1 and 99, inclusive, ^ is displayed once.
• When the rating is between 100 and 199, inclusive, ^ is displayed twice.
• When the rating is between 200 and 299, inclusive, ^ is displayed three times.
• When the rating is between 300 and 399, inclusive, ^ is displayed four times.

Currently, Takahashi's rating is R. Here, it is guaranteed that R is an integer between 1 and 299, inclusive.
Find the minimum increase in rating required for him to increase the number of displayed ^.
It can be proved that under the constraints of this problem, he can increase the number of ^ without raising his rating to 400 or above.

Constraints

• 1 \leq R \leq 299
• R is an integer.

Sample Input 1

123

Sample Output 1

77

Takahashi's current rating is 123, and ^ is displayed twice.
By increasing his rating by 77, his rating will become 200, and ^ will be displayed three times. When the rating is 199 or below, ^ is displayed not more than twice, so print 77.

Sample Input 2

250

Sample Output 2

50

Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.