that had overthrown it during the reigns of the previous emirs. These new Berbers "lacked any familiarity with the pattern of relationships" that had existed in al-Andalus in the 700s and 800s; thus they were not involved in the same web of traditional conflicts and loyalties as the previously already existing Berber garrisons. New frontier settlements were built for the new Berber mercenaries. Written sources state that some of the mercenaries were placed in Calatrava, which was refortified. Another Berber settlement called , west of Toledo, is not mentioned in the historical sources, but has been excavated archaeologically. It was a fortified town, had walls, and a separate fortress or alcazar. Two cemeteries have also been discovered. The town was established in the 900s as a frontier town for Berbers, probably of the Nafza tribe. It was abandoned soon after the Castilian occupation of Toledo in 1085. The Berber inhabitants took all their possessions with them. In the 900s, the Umayyad caliphate faced a challenge from the Fatimids in North Africa. The Fatimid Caliphate of the 10th century was established by the Kutama Berbers. After taking the city of Kairouan and overthrowing the Aghlabids in 909, the Mahdi Ubayd Allah was installed by the Kutama as Imam and Caliph, which posed a direct challenge to the Umayyad's own claim. The Fatimids gained overlordship over the Idrisids, then launched a conquest of the Maghreb. To counter the threat, the Umayyads crossed the strait to take Ceuta in 931, and actively formed alliances with Berber confederacies, such as the Zenata and the Awraba. Rather than fighting each other directly, the Fatimids and Umayyads competed for Berber allegiances. In turn, this provided a motivation for the further conversion of Berbers to Islam, many of the Berbers, particularly farther south, away from the Mediterranean, being still Christian and pagan. In turn, this would contribute to the establishment of the Almoravid dynasty and Almohad Caliphate, which would have a major impact on al-Andalus and contribute to the end of the Umayyad caliphate. With the help of his new mercenary forces, Abd ar-Rahman launched a series of attacks on parts of the Iberian peninsula that had fallen away from Umayyad allegiance. In the 920s he campaigned against the areas that rebelled under Umar ibn Hafsun and refused to submit until the 920s. He conquered Mérida in 928–929, Ceuta in 931, and Toledo in 932. In 934