Bài tập

Một số nguyên dương \(N\) được gọi là số đẹp nếu nó thỏa mãn các điều kiện sau:

• Số đó là số chính phương.
• Tổng các chữ số của nó là một số Fibonacci.

Yêu cầu: Cho số nguyên dương \(N\), đếm số lượng số đẹp nhỏ hơn hoặc bằng \(N\).

Input

Vào từ bàn phím một số nguyên dương \(N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^9\).

Output

Một số nguyên là số lượng số đẹp nhỏ hơn hoặc bằng \(N\).

Example

50

2

Scoring

• Subtask 1: \(60\%\) số test ứng với \(1 \le N \le 10^6\)
• Subtask 2: \(40\%\) số test không có ràng buộc gì thêm.

Nhập vào 4 số nguyên a, b, c, d. In ra số có giá trị nhỏ nhất

Example

80 35 90 55

35

86 52 12 66

12

100 89 89 61

61

16 52 63 25

16

Hoa gọi điện thoại cho Huệ để trao đổi bài. Cứ mỗi phút dùng điện thoại phải trả số tiền là \(x\) đồng. Cuộc trao đổi kéo dài \(t\) phút. Em hãy lập trình tính số tiền mà Hoa phải thanh toán cho cuộc trao đổi này. Với \(x\) và \(t\) là các số nguyên dương được nhập vào từ bàn phím.

Example

3 11

33

Xâu đảo ngược là xâu mà các kí tự được viết ngược từ phải sang trái các kí tự của xâu ban đầu.
Ví dụ: xâu ban đầu là "ab123cd" thì xâu đảo ngược là "dc321ba".

Em hãy tìm tổng của các số có trong xâu đảo ngược của xâu ban đầu.

Input

Vào từ tệp SOTRONGXAU.INP chứa xâu có \(N\) kí tự gồm chữ cái và chữ số
(gồm chữ cái từ 'a' đến 'z' và chữ số từ '0' đến '9').

Output

Ghi vào tệp SOTRONGXAU.OUT là tổng của các số có trong xâu đảo ngược của xâu ban đầu.

Example

abc12gh45

75

Scoring

• 70% số test ứng với 70% số điểm: \(2 < N \le 8\).
• 30% số test ứng với 30% số điểm: \(8 < N \le 16\).