Lớp của Hào có ~50~ bạn. Thầy giáo chủ nhiệm chia cả lớp thành ~4~ tổ theo quy tắc sau:

• Nếu số thứ tự của một học sinh chia hết cho ~4~ thì học sinh ấy ở tổ 4.
• Nếu số thứ tự của một học sinh chia cho ~4~ dư ~3~ thì học sinh ấy ở tổ ~3~.
• Nếu số thứ tự của một học sinh chia cho ~4~ dư ~2~ thì học sinh ấy ở tổ ~2~.
• Nếu số thứ tự của một học sinh chia cho ~4~ dư ~1~ thì học sinh ấy ở tổ ~1~.

Hào muốn biết một bạn có số thứ tự ~n~ thuộc tổ mấy. Bạn hãy giúp Hào nhé!

Input Specification

• Một số ~n~ duy nhất (~1 \leq n \leq 50~) là số thứ tự của một học sinh.

Output Specification

• In ra một số là tổ của bạn học sinh có số thứ tự ~n~.

Sample Case(s)

Input #1:

1

Output #1:

1

Input #2:

27

Output #2:

3

Input #3:

50

Output #3:

2

Trong bài toán Tháp Hà Nội, có ~N~ đĩa theo thứ tự từ nhỏ đến lớn đang nằm ở cột ~A~ như hình bên dưới:

Cần chuyển ~N~ đĩa trên từ cột A sang cột C (lấy cột B làm cột trung gian) theo quy tắc:

• Mỗi lần chỉ được chuyển một đĩa.
• Đĩa nhỏ phải nằm trên đĩa lớn tại bất kì thời điểm nào trong quá trình chuyển.

Vậy để chuyển ~N~ đĩa từ cột A sang cột C theo quy tắc trên thì phải chuyển ít nhất bao nhiêu lần?

Input Specification

• Một số nguyên ~N~ duy nhất (~1 \leq N \leq 100~).

Output Specification

• In ra số lần chuyển tối thiểu để chuyển hết ~N~ đĩa từ cột A sang cột C. Vì kết quả có thể rất lớn nên chỉ in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Sample Case(s)

Input #1:

3

Output #1:

7

Explanation:

• Ở ví dụ thứ nhất, vì ~N = 3~ nên để chuyển ~3~ đĩa từ cột A sang cột C thì cần ít nhất ~7~ bước. Vì ~7~ chia lấy dư cho ~10^9 + 7~ vẫn bằng ~7~ nên in ra màn hình ~7~.

Thực hiện biến đổi một số nguyên dương theo quy tắc sau:

• Nếu số đó là số chẵn, chia nó cho ~2~.
• Nếu số đó là số lẻ, nhân nó với ~3~ và cộng thêm ~1~.

Giả thuyết Collatz chỉ ra rằng chúng ta có thể bắt đầu với bất kì số nguyên dương nào và thực hiện quy tắc trên nhiều bước, chúng ta sẽ cuối cùng sẽ kết thúc ở số ~1~ sau khi thực hiện hữu hạn các bước.

Viết chương trình mô phỏng quá trình thực hiện và in ra một số sau mỗi bước.

Input Specification

• Một số nguyên dương ~N~ (~1 \leq N \leq 10^6~).

Output Specification

• In ra một số sau mỗi bước thực hiện trên một dòng riêng biệt.

Sample Case(s)

Input #1:

12

Output #1:

6
3
10
5
16
8
4
2
1

Explanation:

• Chúng ta bắt đầu từ số ~12~, quá trình có thể được mô tả như sau: $$12 - 6 - 3 - 10 - 5 - 16 - 8 - 4 - 2 - 1$$

Chúng ta có một đường tròn và các số lần lượt từ ~1~ đến ~N~ được viết lên đó (~1~ bên cạnh ~2~, ~2~ bên cạnh ~3~, ~\dots~, ~N~ bên cạnh ~1~). Rick sẽ lần lượt xóa đi mỗi cặp số liền kề rồi tính tích của ~N - 2~ số còn lại. Sau đó, anh ấy sẽ tính tổng của tất cả tích thu được. Vậy kết quả Rick thu được sẽ là bao nhiêu?

Input Specification

• Một dòng duy nhất chứa số nguyên ~N~ (~3 \leq N \leq 20~).

Output Specification

• In ra một số nguyên duy nhất, là tổng của các tích bên trên.

Sample Case(s)

Input #1:

20

Output #1:

2432902008176640000

Input #2:

4

Output #2:

24

Explanation:

• Trong ví dụ thứ hai, ~N = 4~ nên ta sẽ có thể xóa các cặp ~(1, 2)~, ~(2, 3)~, ~(3, 4)~ và ~(4, 1)~. Sau đó ta sẽ có kết quả là $$3 \times 4 + 1 \times 4 + 1 \times 2 + 2 \times 3 = 24$$

Bạn được cho một chuỗi DNA: là một chuỗi bao gồm các kí tự A, C, G và T. Nhiệm vụ của bạn là tìm ra chuỗi con có chứa nhiều kí tự liên tiếp giống nhau nhất.

Input Specification

• Một dòng duy nhất là chuỗi DNA bạn được cho gồm ~N~ kí tự (~1 \leq N \leq 10^6~).

Output Specification

• In ra một số nguyên duy nhất, là độ dài của chuỗi con có nhiều kí tự liên tiếp giống nhau nhất.

Sample Case(s)

Input #1:

CTCAGGTCCG

Output #1:

2

Explanation:

• Trong ví dụ trên, ta thấy có chuỗi con GG và CC là bao gồm nhiều kí tự liên tiếp giống nhau nhất. Vậy nên câu trả lời là ~2~.