Cho số nguyên dương N. Hãy tính tích các chữ số của N.

Dữ liệu vào:

Một số nguyên dương N ~(1≤ N ≤ 10^{18})~.

Kết quả:

Một số là tích các chữ số của N.

Ví dụ

Input

125

Ouput

10

Cho số nguyên dương n, hãy biến đổi n thành F(n) một số lần cho đến khi n=1. Biết F(n) được cho bởi công thức sau:

F(n) =

• n / 2 nếu n chẵn

• 3n + 1 nếu n lẻ

Ví dụ với n = 5, các phép biển đổi được biểu diễn như sau:

• 5 → 16 → 8 → 4 → 2 → 1.

• Số phép biến đổi thực hiện là 5.

Dữ liệu

• Dòng đầu tiên chứ số nguyên dương T ~(T≤10^3)~.

• T dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N_i (N_i≤10^6~)

Kết quả:

Ghi kết quả ra T dòng, dòng thứ i ghi ra số phép biến đổi tương ứng với số ~N_i~. Biết rằng số phép biến đổi luôn hữu hạn.

Ví dụ

Input

3

5

1

2

Output

5

0

1

Cho mảng A gồm n phần tử. Hãy đếm xem mảng này có bao nhiêu phần tử có giá trị bằng số nguyên x.

Input:

Dòng 1 gồm hai số nguyên n và x. ~(0 < n <= 10^6)~, ~x<=10^9~

Dòng 2 gồm n số nguyên tương ứng là n phần tử của mảng A. ~A_i <=10^9~

Ouput

In ra số lần xuất hiện của x trong mảng A.

Ví dụ

Input

6 2

1 2 3 2 2 5

Output

3

Cho mảng ~A~ có ~n~ phần tử ~(n<=10^6)~. Viết chương trình tìm số lớn nhất trong mảng.

Input:

Dòng 1 gồm một số nguyên ~n~ ~(0 < n <= 10^6)~

Dòng 2 gồm n số nguyên tương ứng là n phần tử của mảng ~A_i <=10^9~

Ouput

In ra số lớn nhất của mảng A.

Ví dụ

Input

6

1 2 3 2 2 5

Output

5

Cho dãy số gồm n phần tử ~a_1, a_2, …, a_n~. Hãy đếm các cặp số có tổng bằng 0

Dữ liệu vào:

• Dòng 1 gồm số nguyên dương n

• Dòng 2 gồm n số nguyên ~a_1, a_2, …, a_n~

Kết quả:

• In ra màn hình số lượng cặp số có tổng bằng 0

Ví dụ

Input

5

1 3 1 -1 6

Output

2