You are given ~n~ integers from ~1~ to ~n~. You need to color each integer using one of the colors from ~1~ to ~k~. Thus, each coloring corresponds to a sequence of integers ~c_1, c_2, \ldots, c_n~, where ~c_i~ is the color assigned to the integer ~i~.

A coloring is called harmonious if the following condition holds: there do not exist two distinct integers ~x~ and ~y~ with the same color such that ~x~ divides ~y~. In other words, for every pair of integers ~(x, y)~ such that ~1 \le x < y \le n~, if ~c_x = c_y~ then ~x \nmid y~.

Find the smallest positive integer ~k~ such that there exists a harmonious coloring using only colors from ~1~ to ~k~, and output one such coloring.

Input

Each test case consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 10^4~). The description of the test cases follows.

Each test case consists of a single line containing one integer ~n~ (~1 \le n \le 5 \cdot 10^5~) — the number of integers to color.

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

Output

For each test case, print the result in the following format:

• The first line contains the smallest positive integer ~k~ found.

• The second line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le k~) – a harmonious coloring corresponding to that value of ~k~.

If there are multiple valid harmonious colorings for the smallest positive integer ~k~, output any of them.

Scoring

The total score for this problem is ~1000~.

Sample Input 1

2
3
4

Sample Output 1

2
1 2 2 
3
1 2 2 3

Notes

In the first example, there is no coloring with ~k = 1~. For the only coloring ~c = [1, 1]~, there exists a pair ~(x, y) = (1, 2)~ such that ~c_x = c_y = 1~ and ~x \mid y~, so this coloring is not harmonious.