Thành phố X có ~n~ ngồi nhà và ~m~ đường nối 2 chiều giữa các ngôi nhà. Bọn khủng bố muốn phá huỷ tất cả các ngôi nhà trong thành phố X, khi phá huỷ xong ~1~ ngôi nhà thì những ngôi nhà cạnh nó đều biết tin tức và bàn tán với nhau. Bọn khủng bố muốn phá huỷ theo một thứ tự sao cho sau khi phá huỷ một ngôi nhà thì những ngôi nhà cạnh nó còn lại đều nối với nhau.

Input

Gồm nhiều bộ test mỗi bộ test dòng đầu tiên là 2 số ~n, m~, dòng thứ 2 là ~n~ số lịch trình phá huỷ của bọn khủng bố, ~m~ dòng tiếp theo mỗi dòng gồm 2 số ~a, b~ là chỉ số của 2 ngôi nhà được nối với nhau. ~(1 \leq n \leq 5000, 1 \leq a,b \leq n)~

Output

Gồm nhiều dòng mỗi dòng in ra kết quả của 1 test (“YES” nếu đạt được điều bọn khủng bố muốn, “NO” nếu không)

Example

5 7 
3 2 1 4 5
1 2
1 3
1 4
1 5
2 3
2 5
4 5
4 4
1 2 3 4
1 2
1 4
2 3
3 4

YES
NO

Số đẹp là một số nguyên dương với bất kỳ chữ số lẻ nào ~(1, 3, 5, 7, 9)~ đều xuất hiện lẻ lần nếu nó xuất hiện và bất kỳ chữ số chẵn nào ~(0, 2, 4, 6, 8)~ cũng xuấn hiện chẵn lần nếu nó xuất hiện. Ví dụ số ~141222124~ là một số đẹp, ~f_n~ là là số lượng số đẹp có không quá ~n~ chữ số. Yêu cầu bạn với một số ~n~ tính ~f_n~ mod ~1000000123~.

Input

Gồm nhiều dòng mỗi dòng là một số ~n (1 \leq n \leq 10^{18})~

Output

Gồm nhiều dòng mỗi dòng là kết quả của 1 test

Example

7 
100

287975
123864868

Một số được gọi là tự do nếu như trong biểu diễn thập phân của số đấy không có bất kỳ substring nào của nó là luỹ thừa của ~11~ trừ trường hợp số ~1~. Ví dụ số ~2404~ và ~13431~ là số tự do nhưng số ~911~ và số ~4121331~ không phải số tự do. ~F_n~ là số tự do thứ ~n~, cho số ~n~ yêu cầu bạn tính ~F_n~.

Input

Gồm nhiều dòng mỗi dòng là một số ~n (1 \leq n \leq 10^{18})~

Output

Gồm nhiều dòng mỗi dòng là là kết quả

Example

3
200
500000

3
213
531563

Các ninja làng IOI cần giết ~n~ người tại ~n~ địa điểm khác nhau được đánh dấu từ ~1~ đến ~n~. Các địa điểm được nối với nhau bởi ~m~ con đường ~1~ chiều. Mỗi ninja có thể xuất phát từ một địa điểm nào đó đi trên một lộ trình nào đó và giết sạch những người trên lộ trình đấy (lộ trình có thể rất lòng vòng). Hỏi cần tối thiểu bao nhiêu ninja để có thể hoàn thành nhiệm vụ.

Input

Dòng đầu tiên là số testcase, ~T \leq 70~.

Mỗi case bắt đầu bằng một dòng trống, dòng thứ 2 ghi 2 số ~n (1 \leq n \leq 1000)~ và số ~m (0 \leq m \leq 10000)~. ~m~ dòng tiếp theo là 2 số ~u, v~ tức là có đường một chiều nối địa điểm ~u~ với địa điểm ~v~.

Output

Với mỗi test ghi ra trên một dòng “Case “ + case number + “: “ + kết quả.

Example

3 
5 4 
1 2
1 3
4 1
5 1
7 0
8 8
1 2
2 3
3 4
4 1
1 6
6 7
7 8
8 6

Case 1: 2
Case 2: 7
Case 3: 2

RR là một tay chơi ở casino. Trên bàn casino có ~n~ hàng và ~m~ cột, trên mỗi ô có một con số, RR có ~k~ quân domino ~(1 \times 2)~ trên tay, RR phải đặt toàn bộ các quân domino xuống bàn sao cho chúng không đè lên nhau. Số tiền RR thu được sẽ bằng tổng của tích 2 số của những ô nằm trên vị trí của quân domino.

Input

Gồm nhiều bộ test mỗi test dòng đầu tiên là 3 số ~n, m, k (1 \leq n, m \leq 30, 1 \leq k \leq 200)~

~n~ dòng sau mỗi dòng ~m~ số là số được ghi tại một ô ~(1 \leq a_{ij} \leq 100)~

Output

Với mỗi test in số tiền lớn nhất mà RR có thể kiếm được

Example

2 2 2
1 4
3 2
3 3 1
9 1 1
1 4 4
1 4 4

11
16