K. Pleasure of Hope
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

'Tis distance lends enchantment to the view, and robes the mountain in its azure hue.

Thus, with delight, we linger to survey the promised joys of life's unmeasured way.

Thus, from afar, each dim-discovered scene more pleasing seems than all the past hath been,

And every form, that Fancy can repair from dark oblivion, glows divinely there.

Thomas Campbell, Pleasure of Hope

You are given an integer $$$n$$$ and $$$q$$$ pairs of integers $$$(l_j,r_j)$$$. Construct a sequence $$$a$$$ such that:

  1. $$$a$$$ contains $$$n$$$ distinct positive integers.
  2. For all $$$1\le i \lt n$$$, $$$\gcd(a_i,a_{i+1})=1$$$.
  3. For all $$$1\le j\le q$$$, $$$\displaystyle\sum_{k=l_j}^{r_j}a_k$$$ is a composite number$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$An integer $$$n$$$ is a composite number if and only if it has at least three distinct divisors.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le q \le n \le 4\cdot10^4$$$).

Each of the following $$$q$$$ lines of each test case contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4\cdot10^4$$$.

Output

For each test case, output $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le10^{18}$$$, $$$\sum_{i=1}^{n}a_i \le 10^{18}$$$). It can be shown that a solution always exists under the given constraints.

Example
Input
2
1 1
1 1
4 2
1 3
2 4
Output
114514
1 2 3 4