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ỏa 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

Số nguyên dương ~n~ (~n \le 10^9~)

OUTPUT

Số lượng các cặp số đặc biệt tìm được

SAMPLE INPUT

3

SAMPLE OUTPUT

1

Giải thích: Có ~1~ cặp số đặc biệt ~x = 2~, ~y = 1~ thỏa 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

Ba số nguyên dương ~k, m~ và ~x~, mỗi số không vượt quá ~10^9~

OUTPUT

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

• 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

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 tại 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 ≤ i ≤ 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

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

OUTPUT

Tổng điểm dự đoán đú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 hay 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~.