Metropolitan University Inter University Programming Contest - Sylhet Division 2024
A. GCD Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$. In one operation, you can select two indices $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n)$$$ such that $$$\operatorname{gcd}(p_i, p_j) = 1$$$ and swap the elements at those indices. Here, $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$.

You need to sort the permutation $$$p$$$ into ascending order using at most $$$2 \cdot n$$$ operations. Print the number of operations and the sequence of swaps needed to sort the permutation.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of the permutation and the second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — a permutation of integers from $$$1$$$ to $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, in the first line, print an integer $$$x$$$ $$$(0 \le x \le 2 \cdot n)$$$, the number of operations performed. Then, print $$$x$$$ lines, each containing two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n)$$$, which indicates a swap between the $$$i$$$-th and $$$j$$$-th elements of $$$p$$$.

If there are multiple ways to achieve the result, print any valid sequence of operations. It can be shown that a solution always exists under the given constraints. Note that you do not have to minimize the number of operations.

Example
Input
5
5
3 1 2 5 4
3
3 2 1
6
6 2 5 1 3 4
4
1 2 3 4
7
5 2 4 3 1 6 7
Output
3
4 5
1 2
2 3
3
2 3
1 3
1 2
7
3 5
1 4
4 5
3 6
6 4
5 6
3 4
0
2
1 5
3 4
Note

In the third test case,

  • Initial permutation: $$$[6, 2, 5, 1, 3, 4]$$$
  • Swap $$$p_3$$$ and $$$p_5$$$: $$$[6, 2, 3, 1, 5, 4]$$$
  • Swap $$$p_1$$$ and $$$p_4$$$: $$$[1, 2, 3, 6, 5, 4]$$$
  • Swap $$$p_4$$$ and $$$p_5$$$: $$$[1, 2, 3, 5, 6, 4]$$$
  • Swap $$$p_3$$$ and $$$p_6$$$: $$$[1, 2, 4, 5, 6, 3]$$$
  • Swap $$$p_6$$$ and $$$p_4$$$: $$$[1, 2, 4, 3, 6, 5]$$$
  • Swap $$$p_5$$$ and $$$p_6$$$: $$$[1, 2, 4, 3, 5, 6]$$$
  • Swap $$$p_3$$$ and $$$p_4$$$: $$$[1, 2, 3, 4, 5, 6]$$$

So we sorted the permutation using $$$7$$$ swaps which is under the limit of $$$2 \cdot n = 2 \cdot 6 = 12$$$ swaps.

In the fourth test case, the permutation is already sorted so no swaps are needed.

B. Modular MEX
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Find the smallest non-negative integer that isn't present in $$$n \bmod 1$$$, $$$n \bmod 2$$$, $$$n \bmod 3, \ldots, n \bmod n$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first and only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output

For each test case, output an integer  — the answer to the problem.

Example
Input
3
1
3
2
Output
1
2
1
Note

In the first test case, $$$[1 \bmod 1] = [0]$$$, hence the smallest non-negative integer that isn't present here is $$$1$$$.

In the second test case, $$$[3\bmod1, 3\bmod2, 3\bmod3] = [0, 1, 0]$$$, hence the smallest non-negative number that isn't present here is $$$2$$$.

C. Too Much Walking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a grid $$$a$$$ of $$$n$$$ rows and $$$n$$$ columns. The cell at the $$$i$$$-th row and $$$j$$$-th column of the grid is denoted by $$$a_{i,j}$$$.

The 3D manhattan distance between two cells $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is defined as $$$|a_{x_1,y_1}-a_{x_2,y_2}|+|x_1-x_2|+|y_1-y_2|$$$. Here, $$$|p|$$$ denotes the absolute value of $$$p$$$.

The maximum walking distance of a cell $$$(x,y)$$$ is the maximum 3D manhattan distance between the cell $$$(x,y)$$$ and all other cells $$$(i,j) \ (1 \leq i,j \leq n)$$$ in the grid.

Your task is to print the sum of the maximum walking distances of all cells in the grid.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of test cases.

The first line of each test case contains one integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$ — the dimension of the grid.

The following $$$n$$$ lines contain $$$n$$$ integers each; the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the $$$i$$$-th row $$$(0 \leq a_{i,j} \leq 10^{9})$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, print the sum of the maximum walking distances of all cells in the grid.

Example
Input
2
2
2 6
4 5
5
3 9 2 0 10
4 7 1 5 5
15 3 3 0 0
5 5 5 3 10
8 4 13 1 5
Output
19
385
Note

In the first test case, for cell $$$(1,1)$$$:

  • 3D manhattan distance between $$$(1,1)$$$ and $$$(1,1) = |2-2|+|1-1|+|1-1| = 0$$$
  • 3D manhattan distance between $$$(1,1)$$$ and $$$(1,2) = |2-6|+|1-1|+|1-2| = 5$$$
  • 3D manhattan distance between $$$(1,1)$$$ and $$$(2,1) = |2-4|+|1-2|+|1-1| = 3$$$
  • 3D manhattan distance between $$$(1,1)$$$ and $$$(2,2) = |2-5|+|1-2|+|1-2| = 5$$$

So the maximum walking distance of cell $$$(1,1) = \operatorname{max}(\{0,5,3,5\}) = 5$$$

Similarly,

The maximum walking distance of cell $$$(1,2) = \operatorname{max}(\{5,0,4,2\}) = 5$$$

The maximum walking distance of cell $$$(2,1) = \operatorname{max}(\{3,4,0,2\}) = 4$$$

The maximum walking distance of cell $$$(2,2) = \operatorname{max}(\{5,2,2,0\}) = 5$$$

So, the sum of the maximum walking distances $$$=5+5+4+5=19$$$

D. Nice (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A number is nice if it contains only the digits $$$6$$$ and $$$9$$$. For example, $$$6$$$, $$$99$$$ and $$$69$$$ are nice numbers but $$$5$$$, $$$63$$$ and $$$169$$$ are not.

You are given an integer $$$n$$$. Find the smallest nice number that is greater than or equal to $$$n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 99$$$) — the number of test cases.

The only line contains an integer $$$n$$$ ($$$1 \le n \le 99$$$).

Output

For each test case, print the smallest nice number that is greater than or equal to $$$n$$$.

Example
Input
3
1
68
99
Output
6
69
99
Note

In the first test case, from $$$1$$$ to $$$5$$$, no number contains only digits $$$6$$$ and $$$9$$$. So, the smallest nice number greater than or equal to $$$1$$$ is $$$6$$$.

In the third test case, $$$99$$$ itself is nice, so $$$99$$$ is the answer.

E. Nice (Medium Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A number is nice if it contains only the digits $$$6$$$ and $$$9$$$. For example, $$$6$$$, $$$99$$$ and $$$69$$$ are nice numbers but $$$5$$$, $$$63$$$ and $$$169$$$ are not.

You are given two integers $$$l$$$ and $$$r$$$. Find the number of integers $$$m$$$, such that $$$l \leq m \le r$$$ and $$$m$$$ is nice.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{5}$$$) — the number of test cases.

The first and only line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$).

Output

For each test case, print the number of nice numbers between $$$l$$$ and $$$r$$$.

Example
Input
4
1 10
66 99
69 6969
123123123123123 123123123123123
Output
2
4
17
0
Note

In the first test case, the nice numbers from $$$1$$$ to $$$10$$$ are $$$6$$$ and $$$9$$$, so the answer is $$$2$$$.

In the second test case, there are $$$4$$$ nice numbers from $$$66$$$ to $$$99$$$ and they are $$$66, 69, 96$$$ and $$$99$$$.

F. Nice (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A number is nice if it contains only the digits $$$6$$$ and $$$9$$$. For example, $$$6$$$, $$$99$$$ and $$$69$$$ are nice numbers but $$$5$$$, $$$63$$$ and $$$169$$$ are not.

Let $$$f(m)$$$ be the number of nice numbers from $$$1$$$ to $$$m$$$.

You are given a digit string $$$s$$$ of length $$$n$$$ consisting of digits from $$$1$$$ to $$$9$$$. Let $$$s[l \ldots r]$$$ be the substring of $$$s$$$ from index $$$l$$$ to $$$r$$$ and $$$f(s[l \ldots r])$$$ be the number of nice numbers from $$$1$$$ to $$$m$$$ where $$$m$$$ is the decimal number represented by the digits of the substring $$$s[l \ldots r]$$$.

Your task is to find the sum, modulo $$$998\,244\,353$$$, of $$$f(s[l \dots r])$$$ over all $$$1 \leq l \leq r \leq n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{5}$$$) — the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$), representing the length of the string.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of digits from $$$1$$$ to $$$9$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

For each test case, print a single integer — the answer to the problem.

Example
Input
3
2
69
3
123
10
1692967321
Output
7
10
4586
Note

In the first test case,

$$$f(s[1 \ldots 1]) = f(6) = |\{6\}|= 1$$$,

$$$f(s[2 \ldots 2]) = f(9) = |\{6, 9\}|= 2$$$,

$$$f(s[1 \ldots 2]) = f(69) = |\{6, 9, 66, 69\}|= 4$$$,

So the answer is $$$1 + 2 + 4 = 7$$$

G. I am Tired of Xor Problems
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$. Consider a sequence $$$c$$$ of length $$$n$$$ such that for each $$$i$$$ from $$$1$$$ to $$$n$$$, you can choose $$$c_i$$$ from either $$$a_i$$$ or $$$b_i$$$. Let $$$f(k)$$$ be the maximum of $$$c_1 \oplus c_2 \oplus \cdots \oplus c_n$$$ if you can choose at most $$$k$$$ values from the array $$$a$$$. Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Find the value of $$$f(k)$$$ for each $$$k$$$ from $$$0$$$ to $$$n$$$.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) – the number of test cases.

Each test case consists of three lines. The first line contains an integer $$$n$$$ ($$$1 \le n \le 2^{20}$$$). The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt n$$$). The third line contains $$$n$$$ space-separated integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2^{20}$$$.

Output

For each test case, print $$$n + 1$$$ space-separated integers $$$f(0), f(1), f(2), \ldots, f(n)$$$.

Example
Input
3
4
1 2 2 2
3 0 0 3
3
0 0 0
0 0 0
2
0 1
1 1
Output
0 2 3 3 3 
0 0 0 0 
0 1 1
Note

In the first test case,

  • $$$f(0) = b_1 \oplus b_2 \oplus b_3 \oplus b_4 = 3 \oplus 0 \oplus 0 \oplus 3 = 0$$$, here we can not choose any element from $$$a$$$
  • $$$f(1) = b_1 \oplus a_2 \oplus b_3 \oplus b_4 = 3 \oplus 2 \oplus 0 \oplus 3 = 2$$$, here we select $$$1$$$ element from $$$a$$$. Note that there are multiple ways to select at most $$$1$$$ element from $$$a$$$ and out of all the ways, the maximum xor value is $$$2$$$.
  • $$$f(2) = a_1 \oplus b_2 \oplus b_3 \oplus a_4 = 1 \oplus 0 \oplus 0 \oplus 2 = 3$$$, here we select $$$2$$$ elements from $$$a$$$.
  • $$$f(3) = b_1 \oplus b_2 \oplus a_3 \oplus a_4 = 3 \oplus 0 \oplus 2 \oplus 2 = 3$$$, here we select $$$2$$$ elements from $$$a$$$. Note that we don't have to select exactly $$$k$$$ elements from $$$a$$$, the condition is that we can select at most $$$k$$$ elements from $$$a$$$.
  • $$$f(4) = a_1 \oplus a_2 \oplus a_3 \oplus a_4 = 1 \oplus 2 \oplus 2 \oplus 2 = 3$$$, here we select $$$4$$$ elements from $$$a$$$.

In the third test case,

  • $$$f(0) = b_1 \oplus b_2 = 1 \oplus 1 = 0$$$
  • $$$f(1) = a_1 \oplus b_2 = 0 \oplus 1 = 1$$$
  • $$$f(2) = a_1 \oplus a_2 = 0 \oplus 1 = 1$$$

H. Break the Walls
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A robot is placed on cell $$$(1,1)$$$ of an $$$n \times m$$$ grid and wants to reach the bottom-right corner at cell $$$(n, m)$$$. The grid contains obstacles represented by '#' and open cells represented by '.'. Cell $$$(1,1)$$$ is guaranteed to be open.

The robot can only move in two directions: down and right. In a regular step, the robot can move into an adjacent open cell. However, it can also break through an obstacle if both its previous step and current step are in the same direction. For instance, if there's an obstacle at $$$(x, y)$$$, the robot can move into it from $$$(x, y-1)$$$ only if it arrived here from $$$(x, y-2)$$$ in the previous step.

The goal is to reach the cell $$$(n, m)$$$ by minimizing the number of obstacles it breaks along the way or determining that it's not possible.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n\cdot m \leq 10^5$$$), the grid's dimensions.

Each of the next $$$n$$$ lines contains a string of $$$m$$$ characters ('.' or '#'), representing a row of the grid.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$

Output

For each test case, output a single integer — the minimum number of obstacles the robot needs to break to reach its goal or print $$$-1$$$ if it isn't possible to reach the goal.

Examples
Input
2
3 3
..#
..#
##.
4 4
.###
.#..
..##
#...
Output
1
0
Input
2
1 6
..##.#
3 1
.
#
.
Output
3
-1

I. Delete the String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$. In one operation, you can select a substring $$$s[l \ldots r]$$$ ($$$1 \leq l \leq r \leq n$$$) and delete it from the string if and only if $$$s_l = s_r$$$.

Determine the minimum number of operations required to delete the entire string.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the string and the second line contains a string $$$s$$$ of length $$$n$$$ consisting of only lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^6$$$.

Output

For each test case, print a single integer — the minimum number of operations required to delete the entire string.

Example
Input
4
6
acabdb
4
aaaa
18
abcdaecfacgahciajc
15
abcdaefcghijcki
Output
2
1
2
5
Note

In the first test case, one possible sequence of operations is first deleting the substring aca and then bdb.

In the second test case, the entire string can be deleted in a single operation since all characters are identical.