Problem Statement

There is a calculator with the buttons 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
When a string x is displayed on this calculator and you press a button b, the resulting displayed string becomes the string x with b appended to its end.

Initially, the calculator displays the empty string (a string of length 0).
Find the minimum number of button presses required to display the string S on this calculator.

Constraints

• S is a string of length at least 1 and at most 1000, consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• The first character of S is not 0.

Sample Input 1

1000000007

Sample Output 1

6

To display 1000000007, you can press the buttons 1, 00, 00, 00, 00, 7 in this order. The total number of button presses is 6, and this is the minimum possible.

Sample Input 2

998244353

Sample Output 2

9

Sample Input 3

32000

Sample Output 3

4

Problem Statement

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 18
• 1 \leq A_i < 10^K
• All input values are integers.

Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

10

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

• The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
• The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
• The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
• The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
• The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

1

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

• Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

Constraints

• S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
• The lengths of S and T are equal.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

• Change S to acbe and append acbe to the end of X.

• Change S to acbc and append acbc to the end of X.

• Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

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

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

You are given positive integers N and M.
Find the smallest positive integer X that satisfies both of the conditions below, or print -1 if there is no such integer.

• X can be represented as the product of two integers a and b between 1 and N, inclusive. Here, a and b may be the same.
• X is at least M.

Constraints

• 1\leq N\leq 10^{12}
• 1\leq M\leq 10^{12}
• N and M are integers.

Sample Input 1

5 7

Sample Output 1

8

First, 7 cannot be represented as the product of two integers between 1 and 5.
Second, 8 can be represented as the product of two integers between 1 and 5, such as 8=2\times 4.

Thus, you should print 8.

Sample Input 2

2 5

Sample Output 2

-1

Since 1\times 1=1, 1\times 2=2, 2\times 1=2, and 2\times 2=4, only 1, 2, and 4 can be represented as the product of two integers between 1 and 2, so no number greater than or equal to 5 can be represented as the product of two such integers.
Thus, you should print -1.

Sample Input 3

100000 10000000000

Sample Output 3

10000000000

For a=b=100000 (=10^5), the product of a and b is 10000000000 (=10^{10}), which is the answer.
Note that the answer may not fit into a 32-bit integer type.