Bạn có ~n~ số nguyên từ ~1~ đến ~n~. Bạn cần tô màu mỗi số nguyên bằng một trong số các màu từ ~1~ đến ~k~. Như vậy, mỗi cách tô màu sẽ tương ứng với một dãy số nguyên ~c_1, c_2, \ldots, c_n~, với ~c_i~ là màu được tô cho số nguyên ~i~.

Một cách tô màu được gọi là hài hoà nếu thỏa điều kiện sau: không tồn tại hai số nguyên ~x~, ~y~ khác nhau nào được tô cùng màu mà ~x~ là ước của ~y~. Nói cách khác, với mọi cặp số nguyên ~(x, y)~ sao cho ~1 \le x < y \le n~, nếu ~c_x = c_y~ thì ~x \nmid y~.

Hãy tìm số nguyên dương ~k~ nhỏ nhất sao cho tồn tại cách tô màu hài hoà nếu chỉ sử dụng các màu từ ~1~ đến ~k~, và chỉ ra một cách tô màu như vậy.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Phần mô tả các test case như sau.

Mỗi test case chỉ gồm một dòng, chứa một số nguyên duy nhất ~n~ (~1 \le n \le 5 \cdot 10^5~) — số lượng số nguyên cần tô màu.

Dữ liệu vào đảm bảo rằng tổng ~n~ qua tất cả các test không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi test case, in ra kết quả theo định dạng sau:

• Dòng đầu tiên gồm số nguyên dương ~k~ nhỏ nhất tìm được.

• Dòng thứ hai gồm ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le k~) – một cách tô màu hài hoà ứng với số nguyên ~k~ trên.

Nếu có nhiều cách tô màu hài hoà hợp lệ ứng với số nguyên dương ~k~ nhỏ nhất tìm được, hãy đưa ra cách tô bất kì.

Scoring

Tổng điểm cho bài này là ~1000~.

Sample Input 1

2
3
4

Sample Output 1

2
1 2 2 
3
1 2 2 3

Notes

Ở ví dụ thứ nhất, không tồn tại cách tô màu có ~k = 1~. Với cách tô màu ~c = [1, 1]~ duy nhất, tồn tại cặp ~(x, y) = (1, 2)~ có ~c_x = c_y = 1~ và ~x \mid y~, nên cách tô màu này không hài hoà.