Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

• after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

• 0 \leq H \leq 23
• 0 \leq M \leq 59
• H and M are integers.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

• The i-th element is between 1 and R_i, inclusive.
• The sum of all elements is a multiple of K.

Constraints

• All input values are integers.
• 1 \le N \le 8
• 2 \le K \le 10
• 1 \le R_i \le 5

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

You are given a string S of length N consisting of 0 and 1.

You can perform the following operation any number of times (possibly zero):

• Choose an integer i satisfying 1 \leq i \leq N, and change S_i from 0 to 1, or from 1 to 0.

Your goal is to make the 1s in S form at most one interval. Find the minimum number of operations required to achieve the goal.

More precisely, the goal is to make S such that there exists a pair of integers (l,r) satisfying both of the following conditions. Find the minimum number of operations required to achieve the goal.

• 1 \leq l \leq r \leq N+1.
• S_i= 1 and l \leq i < r are equivalent for each integer i satisfying 1 \leq i \leq N.

It can be proved that the goal can always be achieved with a finite number of operations.

T test cases are given, so solve each.

Constraints

• 1 \leq T \leq 20000
• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• For each input file, the sum of N over all test cases is at most 2 \times 10^5.
• T,N are integers.

Sample Input 1

3
5
10011
10
1111111111
7
0000000

Sample Output 1

1
0
0

In the first test case, if we perform the operation to change S_1 to 0, the 1s will form one interval. Also, the initial S does not satisfy the condition. Therefore, the answer is 1.

In the second test case, there are no 0s in S, so no operations need to be performed. Therefore, the answer is 0.

In the third test case, there are no 1s in S, so no operations need to be performed. Therefore, the answer is 0.

Sample Input 2

5
2
01
10
1000010011
12
111100010011
3
111
8
00010101

Sample Output 2

0
2
3
0
2