| DJC | Competitive Programming | Codeforces |

Contest 2147 - Codeforces - DJC

Link to the contest Here

A. Shortest Increasing Path

Link

  • time limit per test: 1 second
  • memory limit per test: 256 megabytes

You are at (0,0) in a rectangular grid and want to go to (x,y).

To do so, you are allowed to perform a sequence of steps.

Each step consists of moving a positive integer length in the positive direction of either the x or the y axis.

The first step must be along the x axis, the second along the y axis, the third along the x axis, and so on.

Formally, if we number steps from one in the order they are done:

  • Odd-numbered steps → along the x axis
  • Even-numbered steps → along the y axis

Additionally, each step must have a length strictly greater than the previous one.

Task: Output the minimum number of steps needed to reach (x,y), or −1 if it is impossible.

Input

Each test contains multiple test cases.

  • The first line contains the number of test cases t (1 ≤ t ≤ 10⁴).
  • The description of the test cases follows.
  • Each case contains two integers x and y (1 ≤ x, y ≤ 10⁹).

Output

For each test case, output the minimum number of steps to reach (x,y) or −1 if it is impossible.

Example

Input

10
1 2
5 6
4 2
1 1
2 1
3 3
5 1
5 4
752 18572
95152 2322

Output

2
2
3
-1
-1
-1
-1
-1
2
3

Note

  • In the second test case, you can move to (5,0) by moving 5 along the x-axis and then to (5,6) by moving 6 along the y-axis.
  • In the third test case, you can move to (1,0), then to (1,2), and finally to (4,2).
  • In the fourth test case, reaching (1,1) is impossible since after moving to (1,0) along the x-axis, you are forced to move at least 2 along the y-axis.

B. Multiple Construction

Time limit per test: 1 second
Memory limit per test: 256 megabytes

You are given an integer n.
Your task is to construct an array of length 2⋅n such that:

  1. Each integer from 1 to n appears exactly twice in the array.
  2. For each integer x (1 ≤ x ≤ n), the distance between the two occurrences of x is a multiple of x.

In other words, if pₓ and qₓ are the indices of the two occurrences of x, then |qₓ − pₓ| must be divisible by x.

It can be shown that a solution always exists.

Input

Each test contains multiple test cases.
- The first line contains the number of test cases t (1 ≤ t ≤ 10⁴).
- The next t lines each contain a single integer n (1 ≤ n ≤ 2⋅10⁵).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10⁵.

Output

For each test case, print a line containing 2⋅n integers — the array that satisfies the given conditions.

If there are multiple valid answers, print any of them.

Example

Input


3
2
3
1

Output


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

Note

Visualizer link

  • In the first test case:
  • The number 1 appears at positions 1 and 3 → distance is 2, divisible by 1.

  • The number 2 appears at positions 2 and 4 → distance is 2, divisible by 2.

  • In the second test case:

  • The number 1 appears at positions 1 and 3 → distance is 2, divisible by 1.
  • The number 2 appears at positions 4 and 6 → distance is 2, divisible by 2.

  • The number 3 appears at positions 2 and 5 → distance is 3, divisible by 3.

  • In the third test case:

  • The two occurrences of 1 are at positions 1 and 2 → distance is 1, divisible by 1.

C. Rabbits

Time limit per test: 2 seconds
Memory limit per test: 256 megabytes

You have n flower pots arranged in a line numbered from 1 to n left to right.
Some pots contain flowers, while others are empty.

You are given a binary string s describing which pots contain flowers (si = 1) and which are empty (si = 0).

You also have some rabbits, and you want to take a nice picture of rabbits and flowers.
You want to put rabbits in every empty pot (si = 0), and for each rabbit, you can put it looking either to the left or to the right.

Unfortunately, the rabbits are quite naughty, and they will try to jump, which will ruin the picture.

Rules

  • Each rabbit will prepare to jump into the next pot in the direction they are looking.
  • They won’t jump if:
  • There is a rabbit in that pot already.
  • Another rabbit prepares to jump into the same pot from the opposite side.
  • Rabbits won’t jump out of the borders (a rabbit at pot 1 looking left won’t jump, same for a rabbit at pot n looking right).

Goal

Choose the directions of the rabbits so that they never jump, allowing you to take the picture.
You must determine if there exists a valid arrangement.

Input

Each test contains multiple test cases.

  • The first line contains the number of test cases t (1 ≤ t ≤ 10⁴).
  • The description of each test case follows.

For each test case:
- The first line contains an integer n (1 ≤ n ≤ 2·10⁵).
- The second line contains a binary string s of size n, denoting the occupied and empty pots.

It is guaranteed that the sum of n over all test cases does not exceed 2·10⁵.

Output

For each test case, print "YES" if there exists a configuration of rabbits that satisfies the condition, and "NO" otherwise.

You can output the answer in any case (upper or lower).
For example: "yEs", "yes", "Yes", "YES" are all valid.

Example

Input 


12
4
0100
3
000
8
11011011
5
00100
1
1
5
01011
2
01
7
0101011
7
1101010
5
11001
4
1101
9
001101100

Output 


YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO

Note

Visualizer link

Explanation (Test case 1):
- One valid configuration:
- Rabbit at position 1 → right
- Rabbit at position 3 → left
- Rabbit at position 4 → left

No rabbit will move since:
- Rabbit at pot 1 won’t move to pot 2 (rabbit at pot 3 is looking left).
- Rabbit at pot 3 won’t move to pot 2 (rabbit at pot 1 is looking right).
- Rabbit at pot 4 won’t move to pot 3 (already a rabbit).

Explanation (Test case 2):
- One valid configuration:
- Rabbit at position 1 → left
- Rabbit at position 2 → right
- Rabbit at position 3 → left

No rabbit will move since:
- Rabbit at pot 1 won’t move (border).
- Rabbit at pot 2 won’t move to pot 3 (already occupied).
- Rabbit at pot 3 won’t move to pot 2 (already occupied).

It can be proven no valid arrangement exists in Test case 3.

D Game on Array

E Maximum OR Popcount

F Exchange Queries

G Modular Tetration

H Maxflow GCD Coloring

I1 Longest Increasing Path (Easy Version)

I2 Longest Increasing Path (Hard Version)

| DJC | Competitive Programming | Codeforces |