Con mã (ô S) tấn công các ô vuông (dấu x) trên bàn cờ như hình dưới. Có một bàn cờ kích thước ~4 \times n~, với 4 hàng và ~n~ cột, trong đó ~1 \le n \le 100~. Gọi ~Z~ là tập các ô trên bàn cờ. Các hàng được đánh số thứ tự từ trên xuống dưới, từ 1 đến 4, các cột được đánh số thứ tự từ trái qua phải, từ 1 đến ~n~. Quân mã chỉ có thể được đặt trên các ô không thuộc ~Z~ và hai quân bất kỳ không được ăn nhau. Giả định trong mỗi cột có nhiều nhất một ô thuộc ~Z~. Vì vậy, tập ~Z~ có thể được mô tả bằng chuỗi ~k_1, k_2, \dots, k_n~ trong đó ~k_i~ thuộc ~\{0, 1, 2, 3, 4\}~. Nếu ~k_i = 0~ thì cột ~i~ không có ô nào thuộc ~Z~, ngược lại, ô ở hàng ~k_i~, cột ~i~ thuộc ~Z~.

Yêu cầu: Hãy tính số lượng tối đa của các quân mã ~M~, có thể đặt trên bàn cờ theo quy tắc trên và số lượng ~L~ cách sắp xếp có thể có của ~M~ quân mã trên bàn cờ này.

Input

Dòng đầu tiên là số nguyên dương ~n~ ~(1 \le n \le 100)~.

Mỗi dòng trong ~n~ dòng sau ghi một số 0, 1, 2, 3 hoặc 4.

Output

In ra hai số ~M~ và ~L~.

Scoring

Sample Input 1

2
1
0

Sample Output 1

4 8

Notes

Xếp được tối đa 4 con mã và có 8 cách bố trí hợp lệ như hình trên.