Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

You are given a string S of length N consisting of lowercase English letters and the characters ( and ).
Print the string S after performing the following operation as many times as possible.

• Choose and delete a contiguous substring of S that starts with (, ends with ), and does not contain ( or ) other than the first and last characters.

It can be proved that the string S after performing the operation as many times as possible is uniquely determined without depending on how it is performed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• S is a string of length N consisting of lowercase English letters and the characters ( and ).

Sample Input 1

8
a(b(d))c

Sample Output 1

ac

Here is one possible procedure, after which S will be ac.

• Delete the substring (d) formed by the fourth to sixth characters of S, making it a(b)c.
• Delete the substring (b) formed by the second to fourth characters of S, making it ac.
• The operation can no longer be performed.

Sample Input 2

5
a(b)(

Sample Output 2

a(

Sample Input 3

2
()

Sample Output 3

The string S after the procedure may be empty.

Sample Input 4

6
)))(((

Sample Output 4

)))(((

Problem Statement

There is a grid with H rows and W columns. We will refer to the cell at the i-th row from the top and j-th column from the left as cell (i,j). Each cell has at most one mirror placed on it.

Takahashi is standing on the left side of cell (1,1), and Aoki is standing on the right side of cell (H,W). Takahashi has a flashlight and is shining light from the left side of cell (1,1) toward the right. Here, assume that the flashlight's light does not diffuse and is a light ray that travels straight.

Takahashi's goal is to deliver the flashlight's light to Aoki by using the mirrors in the grid.

There are three types of mirror placements. When light hits a mirror, the direction of the light changes according to the mirror placement. For each mirror placement, the exit direction for each entry direction is as shown in the figures below.

• Type A (no mirror is placed)

• Type B (a mirror is placed on the diagonal connecting the upper-left and lower-right)

• Type C (a mirror is placed on the diagonal connecting the upper-right and lower-left)

The mirror placement on the grid is represented by H strings of length W: S_1,S_2,\ldots,S_H. When the j-th character of S_i is A, cell (i,j) is type A; when it is B, cell (i,j) is type B; when it is C, cell (i,j) is type C.

Takahashi can perform the following operation any number of times to deliver the light to Aoki:

• Choose one cell and change the mirror placement of that cell to a different type.

Find the minimum number of operations needed to deliver the light to Aoki.

You are given T test cases; find the answer for each.

Constraints

• 1\leq T
• 1\leq H,W
• HW\leq 2\times 10^5
• S_i is a string of length W consisting of A, B, C.
• T, H, and W are integers.
• The sum of HW over all test cases is at most 2\times 10^5.

Sample Input 1

4
3 4
ABCB
CACC
BCBA
2 2
CB
AA
1 10
BCBCBCBCBC
10 10
CCAABACAAA
CCCBACACCA
BACAABCBBA
ACCCAACCCA
CCAAAACCBA
AACBBACCAA
BCCCACBBAB
CBBCAACCCC
CBBCCBCBCA
BBACABBACC

Sample Output 1

0
2
10
5

For the first test case, the light can be delivered to Aoki without performing any operations.

For the second test case, by changing the mirror placement of cell (1,1) to type A and the mirror placement of cell (2,2) to type B, the light can be delivered to Aoki as shown in the figure below. It is impossible to deliver the light to Aoki with one or fewer operations, so the answer is 2.

Problem Statement

This problem fully contains Problem C (Operate 1), with K \le 20.
You can solve Problem C by submitting a correct solution to this problem for Problem C.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• K is an integer satisfying \color{red}{1 \le K \le 20}.

Sample Input 1

3
abc
awtf

Sample Output 1

Yes

For example, here is a way to convert abc to awtf with three operations:

• Replace the second character b with w. After the operation, the string becomes awc.
• Replace the third character c with f. After the operation, the string becomes awf.
• Insert t between the second and third characters. After the operation, the string becomes awtf.

Sample Input 2

2
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf with two or fewer operations.

Sample Input 3

17
twothousandtwentyfour
happynewyear

Sample Output 3

Yes