gate. There, he started a great fire and threw his scabbard into the flames. Abd al-Rahman told his men that time had come to go down fighting rather than die of hunger. The gate lifted and Abd al-Rahman's men fell upon the unsuspecting Abbasids, thoroughly routing them. Most of the Abbasid army was killed. The heads of the main Abbasid leaders were cut off, preserved in salt, identifying tags pinned to their ears, and then bundled together in a gruesome package and sent to the Abbasid caliph, who was on pilgrimage at Mecca. Upon receiving the evidence of al-Ala's defeat in al-Andalus, al-Mansur is said to have gasped, "God be praised for placing a sea between us!" Al-Mansur hated, and yet apparently respected Abd al-Rahman to such a degree that he dubbed him the "Hawk of Quraysh" (the Umayyads were from a branch of the Quraysh tribe). Despite such a tremendous victory, Abd al-Rahman had to continuously put down rebellions in al-Andalus. Various Arab and Berber tribes fought each other for varying degrees of power, some cities tried to break away and form their own state, and even members of Abd al-Rahman's family tried to wrest power from him. During a large revolt, dissidents marched on Córdoba itself; However, Abd al-Rahman always managed to stay one step ahead, and crushed all opposition; as he always dealt severely with dissidents in al-Andalus. Problems in the Upper March Zaragoza proved to be a most difficult city to reign over for not only Abd ar-Rahman, but his successors as well. In the year 777–778, several notable men including Sulayman ibn Yokdan al-Arabi al-Kelbi, the self-appointed governor of Zaragoza, met with delegates of the leader of the Franks, Charlemagne. "[Charlemagne's] army was enlisted to help the Muslim governors of Barcelona and Zaragoza against the Umayyad [emir] in Cordoba...." Essentially Charlemagne was being hired as a mercenary, even though he likely had other plans of acquiring the area for his own empire. After Charlemagne's columns arrived at the gates of Zaragoza, Sulayman got cold feet and refused to let the Franks into the city, after his subordinate, al-Husayn ibn Yahiya, had successfully defeated and captured Abd al-Rahman's most trusted general, Thalaba Ibn Ubayd. It is possible that he realized that Charlemagne would want to usurp power from him. After capturing Sulayman, Charlemagne's force eventually headed back to France via a narrow pass in the Pyrenees,