xy

Kaloyan was preparing an exam for his students and found the following problem to be pretty interesting. He wrote two numbers $X$ and $Y$ and wants to find a sequence of integers where the sum of every $X$ consecutive elements (in the sequence) is strictly positive while the sum of every $Y$ consecutive elements is strictly negative.

Task

Kaloyan found out that this sequence cannot be infinitely long. He tried to find a sequence of maximum possible length with the described property. However, it turns out to be rather difficult problem for Kaloyan. Help him by writing a program that finds the maximum length of such a sequence. You should find the answers to $Q$ such pairs $X$ and $Y$. Additionally, you have to find a maximal sequence only for the first query.

Input data

The first line of the standard input contains one integer $Q$ — the number of queries.

Each of the following $Q$ lines contains two integers — $X$ and $Y$.

Output data

On the first line of the standard output you should print $Q$ numbers — $N_1 \ N_2 \dots N_Q$, separated with spaces, where $N_i$ is the answer for the $i$-th query. On the second line you should print $N_1$ integers separated with spaces — a sequence with the desired property for the first query.

Constraints and clarifications

• $1 \leq X, Y, Q \leq 100 \ 000$
• The numbers in the sequence must be between $-10^9$ and $10^9$

Example

stdin

3
3 5
1 5
4 2

stdout

6 4 3
5 -7 5 3 -7 5