in North Africa was completed and the Arabs were able to move across large parts of the Berber world, invading Visigothic Spain through the Strait of Gibraltar, under the command of the allegedly Berber general Tariq ibn-Ziyad. But this happened only after they developed a naval power of their own, and they conquered and destroyed the Byzantine stronghold of Carthage between 695 and 698. The loss of Africa meant that soon, Byzantine control of the Western Mediterranean was challenged by a new and expanding Arab fleet, operating from Tunisia. Muawiyah began consolidating the Arab territory from the Aral Sea to the western border of Egypt. He put a governor in place in Egypt at al-Fustat, and launched raids into Anatolia in 663. Then from 665 to 689 a new North African campaign was launched to protect Egypt "from flank attack by Byzantine Cyrene". An Arab army of 40,000 took Barca, defeating 30,000 Byzantines. A vanguard of 10,000 Arabs under Uqba ibn Nafi followed from Damascus. In 670, Kairouan (modern Tunisia) was established as a base for further invasions; Kairouan would become the capital of the Islamic province of Ifriqiya, and one of the main Arabo-Islamic religious centers in the Middle Ages. Then ibn Nafi "plunged into the heart of the country, traversed the wilderness in which his successors erected the splendid capitals of Fes and Morocco, and at length penetrated to the verge of the Atlantic and the great desert". In his conquest of the Maghreb, Uqba Ibn Nafi took the coastal cities of Bejaia and Tangier, overwhelming what had once been the Roman province of Mauretania where he was finally halted. As the historian Luis Garcia de Valdeavellano explains: Arab attacks on Anatolia and sieges of Constantinople As the first tide of the Muslim conquests in the Near East ebbed off, and a semi-permanent border between the two powers was established, a wide zone, unclaimed by either Byzantines or Arabs and virtually deserted (known in Arabic as al-Ḍawāḥī, "the outer lands" and in Greek as , ta akra, "the extremities") emerged in Cilicia, along the southern approaches of the Taurus and Anti-Taurus mountain ranges, leaving Syria in Muslim and the Anatolian plateau in Byzantine hands. Both Emperor Heraclius and the Caliph 'Umar (r. 634–644) pursued a strategy of destruction within this zone, trying to transform it into an effective barrier between the two realms. Nevertheless, the Umayyads still considered