Biết rằng một số nguyên dương ~n~ nào đó không phải là lũy thừa ~2~ và có ~m~ ước dương. Hỏi số ~2n~ có ít nhất mấy ước dương?

Input

Một số nguyên dương ~m~ duy nhất với ~1 \le m \le 10^{16}~.

Output

Số ước ít nhất có thể có của ~2n~.

Sample input 1

3

Sample output 1

6

Sample input 2

15

Sample output 2

18

Giải thích: trong VD1, theo công thức tính số ước, ta thấy số ~n~ có thể có dạng ~p^2~ với ~p~ lẻ nên ~2n=2p^2~ sẽ có số ước là 6. Ở VD2, số ~n~ có thể có dạng ~p^{14}~ hoặc ~2^2.p^4~ hoặc ~2^4.p^2~ với ~p~ là số nguyên tố lẻ; tương ứng thì số ~2n~ có số lượng ước dương là ~30,20,18~ nên giá trị nhỏ nhất cần tìm là ~18.~

Dennis Vũ là một cậu bé đặc biệt, có đam mê lập trình từ nhỏ. Khi lên ba tuổi, thay vì học bảng cửu chương thì Vũ đã học xử lý bit. Vào một ngày nọ, bố cho Vũ một cặp số ~a, b, c~ nguyên dương và hỏi ~a+b+c~ bằng mấy? Thay vì tính ra giá trị đó, Vũ đã trả lời bố các kết quả

~a\; OR \; b \; OR \; c \text{ và } a \; XOR \; b \; XOR \; c \text{ và } a \; AND \; b \; AND \; c~

làm bố rất sửng sốt. Hỏi Vũ tính có đúng không, và nếu tính đúng thì giá trị ~a+b+c~ bằng mấy?

Input

Ba giá trị ~a\; OR \; b \; OR \; c \text{ và } a \; XOR \; b \; XOR \; c \text{ và } a \; AND \; b \; AND \; c~ mà Vũ tính được, trong đó ~0 \le a, b, c \le 2^{31}.~

Output

Nếu Vũ tính sai, tức là không có bộ số ~a,b,c~ nào thỏa mãn thì in ra ~-1~, ngược lại thì in ra ~a+b+c.~

Sample input 1

15 3 2

Sample output 1

31

Sample input 2

1 100 100

Sample output 2

-1

Số ~n~ được gọi là đẹp nếu thoả mãn đồng thời các điều kiện:

• Có thể biểu diễn ~n~ thành tổng của 2 số dương có cùng tổng các chữ số.
• Có thể biểu diễn ~n~ thành tổng của 3 số dương có cùng tổng các chữ số.

Nhiệm vụ của bạn là trả lời ~q~ truy vấn, trong đó ~1 \le q \le 10^5.~ Mỗi truy vấn gồm hai số L, R với ~1 \le L \le R \le 10^{18}~ và đếm xem trong đoạn ~[L;R]~, có tất cả bao nhiêu số đẹp?

Sample input

2
1 10
2024 2026

Sample output

1
1

Giải thích

Ký hiệu ~S(n)~ là tổng chữ số của số nguyên dương ~n~. Ở ví dụ 1, ta có số đẹp duy nhất là ~6 \in [1;10]~ vì có thể viết ~6=3+3=2+2+2~; ở ví dụ 2, ta có số đẹp duy nhất là ~2025~ vì ~2025 = 2016+9 = 2013+6+6~ vì ~S(2016)=S(9)=9~ và ~S(2013)=S(6)=S(6)=6~, kiểm tra trực tiếp được các số khác thì không thoả mãn.

Cho một số nguyên dương ~n~. Mỗi thao tác cho phép chuyển chữ số đầu tiên từ trái sang xuống cuối (cho phép có chữ số ~0~ đứng đầu). Hỏi nếu được thực hiện tối đa ~k~ thao tác thì có cách nào thu được một số chia hết cho ~11~ hay không?

Input:

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ với ~1 \le n \le 10^{10^6}~ và ~0 \le k \le 10^9~.

Output:

• Một dòng duy nhất chứa chữ YES nếu có thể chia hết, còn ngược lại thì NO.

Sample input 1:

13574 0

Sample output 1:

YES

Sample input 2:

57413 3

Sample output 2:

YES

Sample input 3:

1000 1000

Sample output 3:

NO

Giải thích: trong VD1, ta thấy số ban đầu đã chia hết cho 11 nên dù không được chuyển lần nào (do ~k=0~) nhưng vẫn thỏa mãn, trong VD2, ta thấy ~57413 \to 74135 \to 41357 \to 13574~ thì có số cuối chia hết cho ~11.~ Còn trong VD3 thì cho dù chuyển thế nào cũng không được.

Cho số nguyên dương ~n~. Tìm số nguyên không âm ~k~ nhỏ nhất sao cho tích các số ~1! * 2! * 3! ... * k!~ thì chia hết cho ~n~. Định nghĩa ~x!~ là tích của ~x~ số nguyên dương đầu tiên.

Input

Một dòng duy nhất gồm số ~n~ với ~1 \le n \le 10^{14}.~

Output

Một dòng duy nhất là đáp số của bài toán.

Sample input 1

3

Sample output 1

3

Sample input 2

4

Sample output 2

3

Sample input 3

6

Sample output 3

3

Giải thích

Dễ thấy ứng với ~n=3,4,6~ thì đáp số đều là ~k=3~, vì ~1! * 2! * 3! = 12~ trong khi với ~k=2~ thì ~1! 2! = 2~ đều chưa thỏa mãn được điều kiện.

Subtasks

• Có ~50\%~ test ứng với ~n \le 10^5.~

• Có ~50\%~ test ứng với ~10^5 < n \le 10^{14}.~

Một số nguyên dương ~m~ được gọi là thặng dư bậc hai mod ~n~ nếu như tồn tại số nguyên ~x \in \{1,2,...,n \}~ mà ~m \equiv x^2 \pmod n~. Tiếp theo, ta chỉ quan tâm các thặng dư bậc hai ~x~ trong miền ~1,2,...,n~ mà ~\gcd(n,x)=1~, tạm gọi là thặng dư đẹp.

Ví dụ: xét mod ~9~ thì có ba thặng dư đẹp là ~1,4,7~ vì ~1 \equiv 1^2 \pmod 9, \, 4 \equiv 2^2 \pmod 9, \, 7 \equiv 4^2 \pmod 9~ và các số ~1,4,7~ đều nguyên tố cùng nhau với ~9~. Bài toán đặt ra là với số nguyên dương ~n~ cho trước, hãy đếm xem có bao nhiêu thặng dư đẹp của ~n~?

Input. Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output Đáp số của bài toán.

Sample input

2016

Sample output

36

Cho số nguyên dương ~n~. Hãy đếm số cặp số ~(a,b)~ có tính thứ tự sao cho:

1) ~lcm(a,b) = n.~

2) ~\frac{ab}{a+b}~ là một ước dương của ~n~.

Input

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}~.

Output

Hai số nguyên dương trên cùng một dòng, lần lượt là đáp số cho câu hỏi 1) và 2) ở trên.

Sample input

2

Sample output

3 4

Giải thích

Với ~n=2~, ta thấy:

• Có ~3~ cặp số thỏa mãn là ~(a,b)=(1,2),(2,1),(2,2).~
• Các ước của ~2~ là ~1~ hoặc ~2~. Để có ~\frac{ab}{a+b}=1~ thì ~a=b=2;~ còn để có ~\frac{ab}{a+b}=2~ thì ~(a,b)=(4,4),(6,3),(3,6)~ nên tổng cộng có ~4~ cặp.

Nhân dịp có nhiều cao thủ tham gia contest Hướng tới những vì sao lần đầu của năm 2024, BTC xin dành tặng bài cuối cùng này như một thử thách thú vị: Cho số nguyên dương ~n~ và số nguyên tố ~p < n~. Một số nguyên ~m~ với ~1 \le m \le n~ được gọi là tốt nếu như ~C_n^m~ chia hết cho ~p~. Đếm số lượng số tốt.

Ở đây, hệ số nhị thức ~C_n^m~ xác định bởi công thức ~\frac{n!}{m!(n-m)!}.~

Input

Một dòng duy nhất gồm số nguyên dương ~n~ và số nguyên tố ~p~, trong đó ~1 \le n \le 10^{18}~ và ~2 \le p \le \min \{100,n \}.~

Output

Một dòng duy nhất cho biết số lượng số tốt.

Sample input 1

16 2

Sample output 1

15

Sample input 2

20 19

Sample output 2

17

Subtasks

Trong Ví dụ 1, ta thấy các số tốt sẽ bao gồm ~1,2,...,15~. Trong Ví dụ 2, ta đếm được các số tốt là ~2,3,...,18.~

• Có ~25\%~ số test của đề ứng với ~n \le 100.~

• Có ~25\%~ số test của đề ứng với ~100 < n \le 10^5.~

• Có ~50\%~ số test của đề ứng với ~10^5 < n \le 10^{18}.~