Coding Challenge Alpha VII - by Algorave
A. Try and Cry
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's IPL time and you are the owner of Goa Guardians, and you want your team to qualify for playoffs; hence, you are fixing matches. There are $$$N$$$ teams in the tournament, and the first four qualify for playoffs. The tournament is organized in a round robin format, i.e., each team plays with every other team once, and every match results in a win or loss(no draws) and gets $$$1$$$ point for a win and $$$0$$$ point for a loss. If two teams have the same points, then the team with a higher run rate qualifies.

You can decide the outcome of every match and the run rate of every team. Since winning more matches can be suspicious, find the minimum number of wins with which Goa Guardians can qualify, given that you are deciding the outcome of every match of the tournament.

Input

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

Each test case contains a single integer $$$N (4 \lt N \lt 10^9)$$$ — the number of teams in IPL.

Output

For each test case, print a single integer, the minimum number of wins.

Example
Input
2
5
6
Output
1
1
Note

For the first test case, when there are 5 teams, we can qualify when we win just one match. Consider the following points table:

A - 4 wins

B - 3 wins

C - 2 wins

D - 1 win (Our team of interest)

E - 0 wins

Also, we would not be in the top 4 if we do not win any match. Thus, the optimal answer is 1.

B. And Xor Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the distant land of Bitland, where all things operate based on binary logic, there exists a powerful artifact known as the "Bitstone." For centuries, it has maintained balance and order throughout the kingdom. However, one fateful day, the Bitstone began to lose its power, and chaos spread across the land.

The royal scholars discovered that the artifact's energy, symbolized by a number $$$n$$$, represents the current instability of the Bitstone. The only way to restore balance is to find two magical numbers $$$x$$$ and $$$y$$$ that satisfy the ancient binary laws of Bitland:

1. $$$(x \oplus y) = n$$$

2. $$$(x \& y) = 2n$$$

As a skilled programmer, you have been called upon to find how many such valid pairs $$$(x,y)$$$ exist for a given $$$n$$$ and help restore balance to Bitland before the chaos becomes irreversible.

Input

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

Each test case contains a single integer $$$n (0 \le n \le 10^{15})$$$ — the imbalance of the Bitstone.

Output

For each test case, output a single integer representing the number of distinct valid pairs $$$(x, y)$$$ that can stabilize the Bitstone and restore peace to the kingdom.

Example
Input
7
0
1
8
10
12
17
21
Output
1
2
2
4
0
4
8
Note

For $$$n = 0$$$, we need to find pairs $$$(x, y)$$$ such that:

1. $$$(x \oplus y) = 0$$$ (which means $$$x = y$$$)

2. $$$(x \& y) = 0$$$

The only possible solution in this case is $$$(0, 0)$$$ and the answer is $$$1$$$.

For $$$n = 1$$$, we need to find pairs $$$(x, y)$$$ such that:

1. $$$(x \oplus y) = 1$$$ (which means $$$x$$$ and $$$y$$$ must have a bit difference only at the lowest bit.)

2. $$$(x \& y) = 2$$$ (both $$$x$$$ and $$$y$$$ must have a bit set at the second position.)

So, the valid pairs are $$$(2,3)$$$ and $$$(3,2)$$$, and the answer is $$$2$$$.

C. String Traversal Paradigm 1
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 size $$$n$$$ consisting of lowercase English alphabets $$$(a \space to \space z)$$$. The cost of moving from a character $$$c_i$$$ at index $$$i$$$ to $$$c_j$$$ at index $$$j$$$ is as follows:

  1. If $$$c_i \neq c_j$$$, then cost to move from $$$c_i$$$ to $$$c_j$$$ is $$$|i - j|$$$.
  2. If $$$c_i == c_j$$$, then cost to move from $$$c_i$$$ at $$$i$$$ to $$$c_j$$$ at $$$j$$$ is $$$0$$$ .

You are given $$$q$$$ queries. Each query is of the form : $$$u \space v$$$

where you need to find minimum cost to move from character $$$u$$$ (i.e any index i such that $$$c_i = u$$$) to character $$$v$$$ (i.e any index j such that $$$c_j = v$$$). Print $$$-1$$$ if it's not possible to reach from $$$u$$$ to $$$v$$$(If any of u or v does not exist in string, then print $$$-1$$$).

Input

First line contains $$$n$$$ and $$$q$$$. $$$(1 \leq n \leq 10^5)$$$ $$$(1 \leq q \leq 26 \times 26)$$$

Next line contains string $$$s$$$.

Next $$$q$$$ lines contain: $$$u \space v$$$ $$$(a \leq u, v \leq z)$$$

Output

For each query output minimum cost to move from character $$$u$$$ to character $$$v$$$.

Examples
Input
9 2
aabbcedba
a c
b d
Output
2
1
Input
11 7
dcdcccedceb
e b
d b
e e
b e
e a
a b
d d
Output
1
2
0
1
-1
-1
0
Note

In test case $$$1$$$, we can move from 'a' at index $$$1$$$ to 'b' at index $$$2$$$ in cost of $$$|2-1|=1$$$. Now we can move from 'b' at index $$$2$$$ to 'b' at index $$$3$$$ in cost of $$$0$$$. Now we can reach 'c' at index $$$4$$$ from 'b' at index $$$3$$$ in cost of $$$|3-2|=1$$$. Thus the minimum cost of moving from 'a' to 'c' comes out to be $$$2$$$.

D. String Traversal Paradigm 2
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 size $$$n$$$ consisting of lowercase English alphabets $$$(a \space to \space z)$$$. The cost of moving from index $$$i$$$ $$$(c_i$$$ is character at index $$$i)$$$ to index $$$j$$$ $$$(c_j$$$ is character at index $$$j)$$$ is as follows:

  1. If $$$c_i \neq c_j$$$, then cost to move from $$$c_i$$$ to $$$c_j$$$ is $$$|i - j|$$$.
  2. If $$$c_i == c_j$$$, then cost to move from $$$c_i$$$ at $$$i$$$ to $$$c_j$$$ at $$$j$$$ is $$$K$$$ .

You are given a starting index $$$V$$$. You need to find minimum cost to move from $$$V$$$ to all other indices.

Input

First line contains $$$n$$$, $$$V$$$ and $$$K$$$. $$$(1 \leq n \leq 10^3)$$$ $$$(0 \leq V \leq n-1)$$$ $$$(1 \leq K \leq 10^3)$$$

Next line contains string $$$s$$$.

Output

Output an array $$$D$$$ of size $$$n$$$ where $$$D_i$$$ denotes minimum cost of reaching index $$$i$$$ from $$$V$$$.

Examples
Input
9 0 1
aabbcedba
Output
0 1 2 3 4 4 3 2 1
Input
18 3 3
ababcacaaabbecbadc
Output
3 2 1 0 1 2 3 4 4 4 3 3 4 4 3 4 5 4
Note

In test case $$$1$$$, the minimum cost to move to index $$$4$$$ from index $$$0$$$ is $$$|4-0| = 4$$$. The minimum cost to move to index $$$5$$$ from index $$$0$$$ is also $$$4$$$. We can move from index $$$0$$$ to index $$$8$$$ at cost of $$$1$$$(as $$$c_0 == c_8$$$, so cost is equal to K i.e $$$1$$$) and then from index $$$8$$$ to index $$$5$$$ at cost of $$$3$$$.

E. Restricted Diameter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an undirected tree with $$$N$$$ nodes and $$$N-1$$$ edges, we define restricted diameter for a node $$$i$$$ as maximum distance path between any $$$2$$$ nodes(among all possible combinations) such that path between them contains node $$$i$$$.

For each node $$$i$$$ $$$(1 \leq i \leq N)$$$ print the restricted diameter length.

Input

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

First line of each test case contains an integers $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ - number of vertices in tree.

Next $$$N-1$$$ line describe the edges of the tree. The $$$i^{th}$$$ of these $$$N-1$$$ lines contains two space separated integers $$$u_i$$$ and $$$v_i$$$ denoting an edge between $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i,v_i \leq N)$$$.

(The sum of $$$N$$$ over all testcases won't exceed $$$10^5$$$).

Output

A line containing $$$n$$$ integers denoting restricted diameter length for node $$$i$$$ $$$(1 \leq i \leq N)$$$.

Example
Input
2
4
1 2
2 3
2 4
8
1 2
2 3
1 4
1 5
4 6
4 7
7 8
Output
2 2 2 2 
5 5 5 5 4 4 5 5
Note
Centered unscaled image.

Given above is a graph of test case $$$2$$$. Clearly the diameter of the graph is $$$5$$$. So every node of the diameter is having the restricted diameter equal to $$$5$$$. For nodes $$$5$$$ and $$$6$$$, the restricted diameter is $$$4$$$.

F. Sub Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a permutation$$$^{\dagger}$$$ $$$a$$$ of size $$$n$$$, with elements from $$$1$$$ to $$$n$$$.

Let's define the strength of an array $$$a$$$ of size $$$k$$$ (given all elements are distinct) as follows:-

  1. Create permutation $$$b$$$ of the same length (i.e. $$$k$$$) keeping the relative ordering of the elements in $$$b$$$ the same as of a.
  2. The last element of b (i.e. $$$b_k$$$) is the strength of array $$$a$$$.
For example, strength of array $$$[4,1,10,3]$$$ as $$$a$$$ which is equivalent to $$$[3,1,4,2]$$$ as $$$b$$$ is $$$2$$$.

Find the sum of the strength of all the non-empty subarrays of $$$a$$$.

$$$^{\dagger}$$$Permutation of size $$$k$$$ is an array which contains all integers from $$$1$$$ to $$$k$$$.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t \leq 5\cdot 10^4$$$). The following line contains the description of each test case.

The first line contains two integers $$$n$$$ ($$$1\leq n \leq 10^6$$$) — the size of the array.

The second line contains $$$n$$$ positive integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$...$$$ ,$$$a_n$$$ ($$$1 \leq a_i \leq n$$$) — elements of the array $$$a$$$.

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

Output

Print a single integer representing the sum of the strength of all the non-empty subarrays of $$$a$$$.

Example
Input
3
1
1
3
2 1 3
4
3 4 1 2
Output
1
9
14
Note

For the second test case,

  • strength of subarray $$$[2] \equiv [1]$$$ is $$$1$$$.
  • strength of subarray $$$[1] \equiv [1]$$$ is $$$1$$$.
  • strength of subarray $$$[3] \equiv [1]$$$ is $$$1$$$.
  • strength of subarray $$$[2, 1] \equiv [2, 1]$$$ is $$$1$$$.
  • strength of subarray $$$[1, 3] \equiv [1, 2]$$$ is $$$2$$$.
  • strength of subarray $$$[2, 1, 3] \equiv [2, 1, 3]$$$ is $$$3$$$.
Total strength $$$= 1+1+1+1+2+3 = 9.$$$