وكان عمرو بن العاص قد بعث إليها بسرا قبل ذلك وهو محاصر لأهل أطرابلس، فافتتحها. فخلّف عقبة بن نافع جيشه هنالك، واستخلف عليهم عمر بن علىّ القرشى، وزهير بن قيس البلوىّ، ثم سار بنفسه وبمنّ «٢» خفّ معه أربعمائة فارس وأربعمائة بعير، وثمانمائة قربة حتى قدم ودّان فافتتحها، وأخذ ملكهم، فجدع أذنه. فقال: لم فعلت هذا بى وقد عاهدتنى؟ فقال عقبة: فعلت هذا بك أدبا لك، إذا مسست أذنك ذكرته، فلم تحارب العرب. واستخرج منهم ما كان بسر فرضه عليهم، ثلاثمائة رأس وستّين رأسا.
ثم سألهم عقبة: هل من ورائكم أحد؟ فقيل له: جرمة. وهى مدينة فزّان العظمى، فسار إليها ثمانى ليال من ودّان، فلما دنا منها أرسل، فدعاهم إلى الإسلام، فأجابوا، فنزل منها على ستّة أميال، وخرج ملكهم يريد عقبة، وأرسل عقبة خيلا فحالت بين ملكهم وبين موكبه، فأمشوه راجلا حتى أتى عقبة وقد لغب، وكان ناعما، فجعل يبصق الدم، فقال له: لم فعلت هذا بى وقد أتيتك طائعا؟ فقال عقبة: أدبا لك إذا ذكرته لم تحارب العرب. وفرض عليه «٣» ثلاثمائة عبد وستين عبدا. ووجّه عقبة الرحّل «٤» من يومه ذلك إلى المشرق.
ثم مضى على جهته من فوره ذلك إلى قصور فزّان، فافتتحها قصرا قصرا، حتى انتهى إلى أقصاها فسألهم: هل من ورائكم أحد؟ قالوا: نعم، أهل خاوار، وهو قصر عظيم على رأس المفازة فى وعورة على ظهر جبل، وهو قصبة كوار.
٢٢٢