Ngày thứ nhất bố cho Dino ~X~ đồng; ngày thứ hai mẹ cho Dino ~Y~ đồng;
ngày thứ ba bố cho Dino ~X~ đồng; ngày thứ tư mẹ cho Dino ~Y~ đồng;...
Cứ ngày có thứ tự lẻ thì bố cho Dino ~X~ đồng, ngày có thứ tự chẵn thì mẹ cho Dino ~Y~ đồng.

Yêu cầu:
Hỏi sớm nhất đến ngày bao nhiêu thì Dino có ít nhất ~N~ đồng để mua món đồ chơi yêu thích của mình.

Input

• Nhập vào ba số tự nhiên ~X, Y, N~ (mỗi số trên một dòng).
  > ~(X, Y, N \leq 10^9)~

Output

• In ra số nguyên duy nhất là ngày cần tìm.

Subtasks

• Subtask 1 (~70\%~ số điểm): ~X, Y, N \leq 10^6~
• Subtask 2 (~30\%~ số điểm): ~X, Y, N \leq 10^9~

Sample Test

Input

5
2
6

Output

4

Input

5
2
15

Output

5

Note

• Trong ví dụ đầu, sau 4 ngày Dino nhận được: 5 (ngày 1) + 2 (ngày 2) + 5 (ngày 3) + 2 (ngày 4) = 14 (đủ tiền).
• Trong ví dụ hai, phải đến ngày 5 Dino mới nhận đủ từ bố và mẹ tổng cộng ≥ 15 đồng.

Cho tam giác gồm các ô ký tự xếp liên tiếp nhau theo hình tháp tam giác.
Các ô được điền từ trên xuống dưới, từ trái sang phải, tạo thành các xâu "TINHOCTRE" lặp lại liên tiếp.

Yêu cầu:
Hỏi ô đầu tiên của hàng thứ ~N~ là ký tự gì?

Input

• Một số tự nhiên ~N~
  > ~(N \leq 10^6)~

Output

• In ra ký tự đầu tiên của hàng thứ ~N~

Subtasks

• Subtask 1 (~60\%~ số điểm): ~N \leq 1000~
• Subtask 2 (~40\%~ số điểm): ~N \leq 10^6~

Sample Test

Input

3

Output

H

Input

6

Output

T

Note

• Các ô được điền theo thứ tự: T I N H O C T R E T I N H O C T R E T ...
• Tổng số ô trước hàng ~N~ là: ~1 + 2 + ... + (N-1) = (N-1) * N / 2~
• Ô đầu tiên của hàng thứ ~N~ chính là vị trí: ~(N-1)*N/2 + 1~ trong dãy ký tự trên

Cho dãy số: ~1, 1 × 2, 1 × 2 × 3, 1 × 2 × 3 × 4, ...~ (Số thứ ~N~ là tích của các số từ 1 đến ~N~).

Hỏi chữ số cuối cùng khác 0 của số thứ ~N~ trong dãy là chữ số nào?

Input

• Nhập vào một số tự nhiên ~N~ (~1 \leq N \leq 10^4~).

Output

• In ra chữ số cuối cùng khác 0 của số thứ ~N~ trong dãy.

Example

Input

3

Output

6

Input

6

Output

2

Giải thích

• Với ~N = 3~, ta có: ~1 × 2 × 3 = 6~ → chữ số cuối cùng là 6.
• Với ~N = 6~, ta có: ~1 × 2 × 3 × 4 × 5 × 6 = 720~ → chữ số cuối cùng khác 0 là 2.

Scoring

• 60 điểm nếu chương trình chạy đúng với ~N \leq 15~.
• 100 điểm nếu chương trình chạy đúng với ~N \leq 10^4~.