Програмчлалын олимпиадын бодлогын архив

N ширхэг хот байгаа ба тэдгээр нь хоорондоо замаар холбогдсон байна. Зам болгон хоёр л хотыг холбох ба хоёр хот нэг л замаар холбогдож болно. Хотуудын холболтын мэдээлэл өгөгдсөн бол тойрон аялалд хамрагдаж болох бүх замуудыг ол. Тойрон аялал гэдэг нь А хотоос эхлээд түүн дээр ирж дуусч буй замуудын дарааллыг хэлнэ. Үүнд А-гаас бусад хотууд нэг л удаа оролцоно. Дор хаяж нэг аялал байгаа гэж үз.

Input

Эхний мөрөнд хотуудын тоог илэрхийлэх N (N<=20) тоо оршино. Дараагийн N мөрөнд хотуудын холбогдсон байдлыг матриц байдлаар дүрсэлнэ. Мөр бүрт N ширхэг тоо байх ба зайгаар тусгаарлагдсан байна. Хэрэв энэ дүрслэлийн L дэх мөрийн C дэх багана дээр 0 гэсэн тоо байвал энэ хоёр хот замаар холбогдоогүй гэсэн үг. Эсрэг тохиолдолд энэ хоёр хотыг шууд холбосон зам байна.

Output

Ядаж нэг тойрон аялалд хамрагдаж байгаа ирмэгүүдийн тоо M-г хэвлэнэ.

Example

Input:
6
0 1 1 0 0 0
1 0 1 1 0 0
1 1 0 0 0 1
0 1 0 0 1 0
0 0 0 1 0 1
0 0 1 0 1 0


Output:
7