Cho trước số nguyên dương ~n~. Hai số nguyên dương ~x~ và ~y~ gọi là cặp số đặc biệt nếu thảo mãn điều kiện ~x^2 - y^2 = n~.

Yêu cầu: Tìm số lượng các cặp số đặc biệt với ~n~ đã cho

Input

Đọc vào file CAU1.INP một số nguyên dương n (~n \le 10^9~)

Output

Ghi ra file CAU1.OUT số lượng các cặp số đặc biệt tìm được

Sample Input

3

Sampel Output

1

Giải thích: Có 1 cặp số đặc biệt ~x = 2, y = 1~ thoả mãn ~x^2 - y^2 = 3~

Cho trước ba số nguyên dương ~k, m~ và ~x~

Yêu cầu: TÌm số dư của phép chia ~x^k~ cho ~m~

Input

Đọc từ file CAU2.INP ba số nguyên dương ~k, m~ và ~x~, mỗi số không vượt quá ~10^9~

Output

Ghi ra file CAU2.OUT số dư tìm được

Sample Input

5 7 4

Sample Output

2

Giải thích: ~4^5~ khi chia cho 7 có số dư là 2

Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, ...., a_n~

Yêu cầu: TÌm ước số chung lớn nhất ~d~ của ~n~ số trong dãy A.

Input

Đọc từ file CAU3.INP 2 dòng:

• Dòng đầu chứa số nguyên dương ~n~, với ~2 \le n \le 10^5~
• Dòng tiếp theo chứa ~n~ số nguyên dương không vượt quá ~10^9~

Output

Ghi ra file CAU3.OUT số ~d~ tìm được

Sample Input

4
8 2 10 4

Sample Output

2

Giải thích: ~d = 2~ là ước chung lớn nhất của 4 số 8, 12, 10 và 4

Trong liên hoan phim thành phố ~X~ có ~n~ bộ phim tham gia tranh giải phim hay nhất và đạo diện xuất sắc nhất. Ban tổ chức nhận được kết quả dự đoán của khán giả qua mạng như sau: Phim thứ ~i~ (~1 \le i \le n~) có tổng điểm dự báo không đạt giải thưởng nào là ~a_i~, đạt giải thưởng phim hay nhất là ~b_i~ và đạt giải thưởng đạo diễn xuất sắc nhất là ~c_i~.

Yêu cầu: Chọn ra hai bộ phim khác nhau ~u~ và ~v~, trong đó ~u~ đạt giải phim hay nhất và ~v~ đạt giải đạo diễn xuất sắc nhất, còn các phim khác không đạt giải nào sao cho tổng điểm dự đoán đúng là lớn nhất.

Input

Đọc từ file CAU4.INP dữ liệu sau:

• Dòng đầu chứa số nguyên dương ~n~, với ~2 \le n \le 10^5~
• Trong ~n~ dòng tiếp, dòng thứ ~i~ (~1 \le i \le n~) chứa 3 số nguyên dương ~a_i, b_i, c_i~, mỗi số không quá ~10^9~

Output

Ghi ra file CAU4.OUT tổng điểm dự đoan đúng lớn nhất tìm được

Sample Input

3
3 6 9
1 5 7
1 3 9

Sample Output

17

Giải thích: Chọn phim ~2~ đạt giải phim hat nhất và phim ~3~ đạt giải đạo diện xuất sắc nhất có tổng điểm dự đoán đúng lớn nhất tìm được là ~3 + 5 + 9 = 17~