Cho số nguyên dương ~n > 1~, tìm số mũ ~m~ nguyên dương lớn nhất có thể có sao cho ~n = a^m~ với ~a~ là số nguyên dương nào đó.

Input

Một giá trị ~n~ duy nhất với ~2 \le n \le 10^{18}.~

Output

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

Sample input

100

Sample output

2

Sau một ngày làm việc vất vả, anh Long sẽ thưởng cho mình bằng những bữa ăn với những chùm nho mẫu đơn ngon lành. Anh ta có ~n~ trái nho được nối với nhau qua ~n-1~ cành, hai trái nho bất kì luôn được nối với nhau qua chuỗi những cành. Long sẽ có ba bữa ăn trong ngày. Để chuẩn bị cho bữa ăn, anh ta sẽ cắt ~2~ cành cây bất kì để có được ~3~ nhánh nho, mỗi nhánh cho mỗi bữa.

Tuy nhiên anh Long không muốn bất kì bữa ăn nào quá ngọt ngào nên anh ấy quyết định cắt sao cho độ chênh lệch giữa nhánh có nhiều nho nhất và ít nho nhất là nhỏ nhất có thể. Bạn phải giúp anh ấy tìm độ chênh lệch đó.

Input

• Dòng đầu chứa số nguyên ~n~ là số lượng nho. Các trái được đánh số từ ~1 \to n~ với ~1 \le n \le 2.10^5 ).~
• Mỗi dòng trong ~n-1~ dòng còn lại gồm ~2~ số nguyên ~x~ và ~y~ với ~1 ≤ x,y ≤ n~ số hiệu 2 trái nho nối trực tiếp với nhau.

Output

In ra độ chênh lệch tối thiểu giữa đùm có nhiều nho nhất và ít nho nhất.

Sample input 1

4
1 2
2 3
3 4

Sample output 1

1

Sample input 2

6
1 2
1 3
3 4
3 5
5 6

Sample output 2

0

Trong các môn học thì anh Lộc thích nhất môn CP, và trong các mảng kiến thức CP, Lộc thích nhất việc dùng cây phân đoạn. Lộc đã luyện nó ngày đêm đến hàng chuyên gia. Một hôm, có anh Aquarius cũng xưng là nghệ nhân về cây phân đoạn đến thử thách anh Lộc một bài toán quen mà lạ như sau: Cho ~n~ số tự nhiên ~a_1,a_2,…,a_n~ và ~2~ loại thao tác:

• Loại 1: tính tổng các phần tử trong đoạn ~[l,r].~
• Loại 2: áp dụng phép toán XOR với ~x~ cho trước cho từng phần tử trong đoạn ~[l,r].~

Cho danh sách ~m~ thao tác thuộc 2 loại trên, anh Lộc cần thực hiện tất cả các thao tác đã cho và đối với mỗi thao tác tính tổng, in ra kết quả nhận được. Anh Lộc đã giải xong subtask 1 dùng vét cạn rồi, còn subtask 2 thì anh... đang suy nghĩ thêm ^^. Bạn hay thử sức nhé, vì nghệ nhân Aquarius hình như cũng đang quên solution rồi T_T.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ và dòng tiếp theo là các số tự nhiên ~a_1,a_2,…,a_n~.
• Dòng thứ 3 chứa số nguyên dương ~m~ là số thao tác và trong ~m~ dòng tiếp theo mô tả ~m~ thao tác theo định dạng:
• ~1~ ~l~ ~r~: Tính tổng phần tử trong đoạn ~[l,r];~
• ~2~ ~l~ ~r~ ~x~: Áp dụng phép toán XOR với ~x~ cho tất cả phần tử trong đoạn ~[l,r].~

Output trả lời tất cả các câu hỏi ở thao tác loại 1.

Sample input

5
4 10 3 13 7
8
1 2 4
2 1 3 3 
1 2 4 
1 3 3 
2 2 5 5
1 1 5
2 1 2 10
1 2 3

Sample output

26
22
0
34
11

Subtasks

• Có 60% test ứng với ~n,m≤2.10^3~ còn ~x, a_i <= 10^6~.
• Có 40% test ứng với ~n≤2.10^5,m≤2.10^5~ còn ~x, a_i≤10^6~.

Một xâu được gọi là đối xứng, nếu nó đọc ngược cũng giống như đọc xuôi. Ví dụ các xâu "z", "aa", "abba", "madam" là đối xứng và các xâu "ab", "abc", "abab" là không đối xứng. Một xâu được gọi là đối xứng đôi, nếu nó được tạo thành bằng cách ghép hai xâu đối xứng có độ dài bằng nhau. Ví dụ các xâu "ab", "aabb", "aaaa" là đối xứng đôi và các xâu "aaa", "abba" và "aaaabb" là không đối xứng đôi.

Cho trước một xâu ~s~, bạn hãy viết một chương trình đếm xem có bao nhiêu xâu con của xâu ~s~ là đối xứng đôi. Nói cách khác, có bao nhiêu cặp ~(l,r)~ sao cho xâu con ~s_l s_{l+1}…s_r~ là đối xứng đôi. Ví dụ, xâu s= "abacac" có 6 xâu con đối xứng đôi là: "ab", "ba", "ac", "ca", "ac", "abacac".

Input dòng đầu tiên chứa số nguyên ~n~ với ~1≤n≤5 \times 10^5~ là độ dài xâu ~s~. Dòng thứ hai chứa xâu ~s~ bao gồm các chữ cái tiếng Anh viết thường.

Output số xâu con đối xứng đôi của xâu ~s~.

Sample input 1

6
abacac

Sample output 1

6

Sample input 2

1
e

Sample output 2

0

Ràng buộc:

• Có ~30\%~ số test của bài thỏa mãn: ~1≤n≤500;~
• Có ~30\%~ số test của bài thỏa mãn: ~1≤n≤5000;~
• Có ~40\%~ số test không có ràng buộc gì thêm.