Hội thi tin học trẻ năm nay có ~k~ thí sinh dự thi. Ban tổ chức đang có ~n~ cái kẹo muốn chia cho các thí sinh sao cho mỗi bạn đều nhận được số kẹo bằng nhau mà không thừa lại chiếc kẹo nào. Em hãy tính giúp ban tổ chức số kẹo ít nhất cần mua thêm để có thể chia đều cho các bạn thí sinh.

Dữ liệu

• Nhập vào hai số tự nhiên ~n~ và ~k~ ~(1 ≤ n, k ≤ 10^9)~, mỗi số được viết trên một dòng.

Kết quả

• In ra một số duy nhất là số kẹo cần mua thêm. Nếu không cần mua thêm in ra 0.

Sample Input 1

10
3

Sample Output 1

2

Note

• Ban tổ chức có ~10~ cái kẹo và ~3~ bạn thí sinh.
• ~10~ cái kẹo chia đều cho ~3~ thí sinh mỗi bạn được ~3~ cái kẹo và thừa lại ~1~ cái kẹo.
• Để không dư chiếc kẹo nào, cần thêm ~2~ cái kẹo nữa (tổng là ~12~ cái kẹo).

Sample Input 2

20
2

Sample Output 2

0

Note

• Ban tổ chức có ~20~ cái kẹo và ~2~ thí sinh.
• ~20~ cái kẹo chia đều cho ~2~ thí sinh mỗi bạn được ~10~ cái kẹo và không thừa lại cái kẹo nào vì vậy không cần mua thêm.

Cho dãy số có quy luật: ~0~, ~3~, ~6~, ~9~, ~12~, ~15~, ~18~, ~21~, ~...~

Em hãy lập trình để đưa ra chữ số cuối cùng của số ở vị trí thứ ~n~ trong dãy trên.

Dữ liệu

• Nhập vào một số tự nhiên duy nhất ~n~ ~(1 ≤ n ≤ 10^9)~.

Kết quả

• Ghi ra một số duy nhất là chữ số cuối cùng của số ở vị trí thứ ~n~ trong dãy.

Chấm điểm

• ~40\%~ số test ứng với ~40\%~ số điểm có: ~n ≤ 10^5~;
• ~30\%~ số test ứng với ~30\%~ số điểm có: ~10^5 < n ≤ 10^6~;
• ~30\%~ số test ứng với ~30\%~ số điểm có: ~10^6 < n ≤ 10^9~.

Sample Input 1

6

Sample Output 1

5

Note

Số ở vị trí thứ ~6~ trong dãy là ~15~ có chữ số cuối cùng là ~5~.

Sample Input 2

10

Sample Output 2

7

Note

Số ở vị trí thứ ~10~ trong dãy là ~27~ có chữ số cuối cùng là ~7~.

An có mật khẩu là chuỗi ký tự ~S~ độ dài không quá ~100~ ký tự, chỉ chứa các chữ cái La tinh (a, ... ,z, A, ... ,Z), chữ số (0, ... ,9), và các ký tự đặc biệt @, #, $, %, &, *.

An muốn nhờ bạn tính độ mạnh mật khẩu của mình. Biết rằng:

• Nếu ~S~ chứa ít nhất một chữ cái thì độ mạnh được cộng thêm ~1~ điểm.
• Nếu ~S~ chứa ít nhất một chữ số thì độ mạnh được cộng thêm ~1~ điểm.
• Nếu ~S~ chứa ít nhất một ký tự đặc biệt thì độ mạnh được cộng thêm ~1~ điểm.
• Nếu độ dài chuỗi ~S~ lớn hơn hoặc bằng ~8~ thì độ mạnh được cộng thêm ~1~ điểm.

Em hãy lập trình tính độ mạnh mật khẩu của An.

Dữ liệu

• Nhập vào một chuỗi ~S~ là mật khẩu của An.

Kết quả

• Ghi ra một số duy nhất là điểm độ mạnh mật khẩu của An.

Sample Input 1

Ab12@#

Sample Output 1

3

Note

• Chữ cái: Ab được cộng ~1~ điểm
• Chữ số: 12 được cộng ~1~ điểm
• Ký tự đặc biệt: @# được cộng ~1~ điểm

An có ~N~ viên bi giống hệt nhau. Một trong số đó có trọng lượng khác các viên còn lại (nhẹ hơn một chút). An không thể tìm ra nó bằng cách quan sát hay ước lượng bằng tay, và cũng không có dấu hiệu nào khác để tìm ra viên bi khác biệt. Cách duy nhất để xác định là cân chúng.

An chỉ có một chiếc cân thăng bằng (hay còn gọi là cân đĩa thăng bằng), cấu tạo của cân có hai đĩa nằm đối xứng nhau. Khi đặt vật nặng lên hai đĩa, bên nặng hơn sẽ hạ xuống, bên nhẹ hơn sẽ cao hơn so với vị trí thăng bằng ban đầu.

Em hãy giúp An tìm số lần cân ít nhất có thể để chắc chắn tìm được viên bi có trọng lượng nhẹ hơn những viên bi còn lại.

Dữ liệu

• Nhập vào một số tự nhiên ~N~ là số viên bi.

Kết quả

• Một số là số lần cân ít nhất để tìm được viên bi có trọng lượng nhẹ hơn.

Chấm điểm

• ~50\%~ số test ứng với ~50\%~ số điểm có: ~n ≤ 10^6~;
• ~50\%~ số test ứng với ~50\%~ điểm còn lại không có thêm ràng buộc nào khác.

Sample Input

12

Sample Output

3

Note

• Lần cân thứ nhất: Chia ~12~ viên bi thành ~2~ nhóm mỗi nhóm ~6~ viên. Sẽ tìm được nhóm ~6~ viên bi nhẹ hơn
• Lần cân thứ hai: Chia ~6~ viên bi thành ~2~ nhóm mỗi nhóm ~3~ viên bi. Sẽ tìm được nhóm ~3~ viên nhẹ hơn.
• Lần cân thứ ba: chọn ~2~ viên bi bất kì để cân. Nếu viên nào nhẹ hơn đó là viên cần tìm. Nếu ~2~ viên cân bằng thì viên cần tìm là viên còn lại.

-