Dế Mèn có 2 số ~L~ và ~R~. Tìm dãy ~a~ độ dài ~k~ bất kỳ thỏa:

• ~a_i~ chia hết cho ~a_{i-1}~.

• các số trong dãy ~a~ phân biệt đôi một.

• ~a_1 = L, a_k = R~.

• ~k~ lớn nhất có thể.

In ra độ dài ~k~ lớn nhất có thể có.

Input

• Dòng duy nhất nhập vào hai số nguyên dương ~L~ và ~R~ (~1 \le L < R \le 10^{15}~).

• Dữ liệu đảm bảo ~R~ chia hết cho ~L~.

Output

In ra một số nguyên ~k~ là độ dài lớn nhất của dãy ~a~ tìm được.

Scoring

Sample Input 1

3 18

Sample Output 1

3

Notes

Dãy ~a~ có thể là ~[3, 9, 18]~.

Ngày mai lớp của ~Lona~ sẽ có buổi kiểm tra Tin học. ~Lona~ rất lo lắng vì đề thầy cho rất khó và hại não. Do đó để có thể được thêm điểm cộng cho bài kiếm tra này thì ~Lona~ đã quyết định sẽ xung phong giải bài tập về nhà.

Thầy giáo cho các bạn trong lớp một số nguyên dương ~n~ và yêu cầu đếm tất cả các số nguyên dương ~s~ thỏa mãn:

• ~s \le n~
• ~s = p^3 \times q^3~ với ~p~ và ~q~ là các số nguyên tố phân biệt.

Loay hoay mãi nhưng ~Lona~ vẫn chưa thể giải được nên đành nhờ các bạn ở ~VNOJ~ giúp đỡ. Là một lập trình thiên tài, bạn hãy giúp đỡ ~Lona~ nhé.

Input

Dòng duy nhất nhập vào một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~.

Output

In ra yêu cầu đề bài: số số nguyên dương ~s~ thỏa mãn.

Scoring

Sample Input 1

1000

Sample Output 1

2

Notes

Có ~2~ số thỏa mãn đề bài:

• ~216 = 2^3 \times 3^3~
• ~1000 = 2^3 \times 5^3~

Nhân dịp trung thu, các bạn tình nguyên viên Bedao được thưởng một thùng toàn là kẹo. Vì em bé FireGhost và TrungNotChung nhỏ nhất nên được ưu tiên lấy kẹo trước. Thùng kẹo có ~k~ viên kẹo nhưng không em nào nhường em nào. Hai em đã nghĩ ra trò chơi như sau:

Cho một dãy có ~n~ phần tử, phần tử thứ ~i~ có giá trị ~1 \leq a_i \leq k~. Mỗi lượt một trong hai em sẽ chọn ra một số nguyên ~a_i~ trong dãy, có giá trị không vượt quá số lượng kẹo còn lại, và bốc ra khỏi thùng kẹo ~a_i~ viên. Các giá trị ~a_i~ có thể được dùng nhiều lần. Trò chơi dừng lại khi không thể bốc được thêm.

Hai em chơi luân phiên theo lượt, FireGhost chơi trước, hãy tìm lượng kẹo nhiều nhất FireGhost có thể bốc được, nếu như cả hai em cùng chơi tối ưu nhé.

Input

• Dòng đầu chứa hai số nguyên dương ~k, n~ ~(1 \leq n \leq 100, 1 \leq k \leq 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \leq a_i \leq k)~ mô tả dãy ~a~.

• Dữ liệu đảm bảo ~a_1 = 1~.

Output

• Gồm một số nguyên duy nhất là lượng kẹo nhiều nhất FireGhost có thể bốc được, nếu như hai em cùng chơi tối ưu.

Sample Input 1

10 3
1 3 4

Sample Output 1

6

Notes

Tại lượt đầu tiên, FireGhost bốc ra khỏi thùng kẹo ~3~ viên.

• Nếu TrungNotChung bốc ra ~4~ viên thì FireGhost bốc ra ~3~ viên, TrungNotChung kết thúc trò chơi với ~4~ viên kẹo.

• Nếu TrungNotChung bốc ra ~3~ viên thì FireGhost bốc ra ~4~ viên, TrungNotChung kết thúc trò chơi với ~3~ viên kẹo.

• Nếu TrungNotChung bốc ra ~1~ viên thì FireGhost bốc ra ~4~ viên. Khi đó, lượng kẹo còn lại là ~2~ viên nên TrungNotChung sẽ kết thúc trò chơi với nhiều nhất là ~3~ viên kẹo.

TrungNotChung chơi tối ưu nên sẽ bốc ra ~4~ viên kẹo và FireGhost bốc ra ~3~ viên kẹo còn lại.

Vậy FireGhost kết thúc trò chơi với ~6~ viên kẹo. Có thể chứng minh đây là lượng kẹo nhiều nhất FireGhost nhận được nếu cả hai bạn chơi tối ưu.

Đếm số dãy ~a~ nguyên dương độ dài ~n~ thỏa mãn:

• ~1 \leq a_i \leq m~

• ~gcd(a_1, a_2, \dots, a_n) = k~.

Input

Dòng duy nhất nhập ~3~ số nguyên dương ~n, m, k (1 \leq n, m, k \leq 10^6)~.

Output

In ra số dãy ~a~ thỏa mãn điều kiện.

Vì đáp án có thể rất lớn, in ra số dãy modulo ~998244353~.

Scoring

Sample Input 1

3 4 2

Sample Output 1

7

Notes

Có các dãy ~a~ sau thỏa ~gcd(a_1, a_2, a_3) = 2~:

• ~(2, 2, 2)~

• ~(4, 2, 2)~

• ~(2, 4, 2)~

• ~(2, 2, 4)~

• ~(4, 4, 2)~

• ~(4, 2, 4)~

• ~(2, 4, 4)~

Cho số nguyên dương ~n~, hãy chia dãy số ~[1^2, 2^2, 3^2, \ldots, n^2]~ thành hai nhóm có tổng bằng nhau.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^3~) — số test case của bài toán.

Mỗi dòng trong ~t~ dòng tiếp theo chứa duy nhất chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).

Dữ liệu đảm bảo tổng của ~n~ trong tất cả các test case không vượt quá ~10^6~.

Output

Với mỗi test case:

• Nếu không tồn tại cách để chia dãy số thành hai nhóm có tổng bằng nhau, in ra NO.

• Ngược lại, in ra YES, sau đó xuống dòng và in ra ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 1~), sao cho ~\sum \limits_{b_i = 0} i^2 = \sum \limits_{b_j = 1} j^2~.

Sample Input 1

2
4
7

Sample Output 1

NO
YES
0 0 1 0 1 1 0

Trong Số học, Phi hàm Euler thường được kí hiệu là ~φ(n)~, là hàm số thể hiện số số nguyên dương không lớn hơn ~n~ và nguyên tố cùng nhau với ~n~. Trong bài này, ta có 2 số nguyên dương ~l~, ~r~, hãy tính giá trị ~φ(l \cdot (l + 1)\cdot \ldots \cdot r)~ ~mod~ ~M~.

Input

Dòng đầu gồm một số nguyên ~M~ (~1 \le M \le 998244353~).

Dòng thứ hai gồm 1 số nguyên ~T~ (~1 \le T \le 2 \cdot 10^5~) — số lượng bộ test.

~T~ dòng cuối cùng, mỗi dòng gồm ~2~ số nguyên dương ~l~, ~r~ (~1 \le l \le r \le 10^6~) thể hiện một truy vấn.

Output

Gồm ~T~ dòng là đáp án của mỗi truy vấn.

Scoring

Sample Input 1

998244353
3
1 2
2 5
5 7

Sample Output 1

1
32
48