OPINION

DAVIS, Circuit Judge:

Appellant Terrence C. Vaughan ("Vaughan") was driving a rental car with McKinley Scott ("Scott") in Virginia when Virginia State Police Officer Steven Homiak ("Homiak") pulled him over for speeding. Based on Scott's apparent nervousness and the presence of four cellular phones in the center console (two of which were pre-paid phones that Homiak associated with "people involved with drugs"), and on Scott's and Vaughan's conflicting explanations for their travels, Homiak called in a drug-detection dog. The dog arrived 13 minutes after the initiation of the traffic stop. It alerted by the trunk two to three minutes later; the resulting search revealed 830.6 grams of cocaine. Vaughan filed a motion to suppress which the district court denied. He then pled guilty, reserving his right to appeal the motion's denial, and was sentenced to 120 months' incarceration. For the following reasons, we affirm.

I.

On January 5, 2011, Homiak, a ten-year veteran of the Virginia State Police, was conducting a routine assignment on Interstate 95 in Greenville, Virginia. Homiak observed a white Ford Taurus pass him traveling northbound at a high rate of speed. After pacing the vehicle at 79 miles per hour in a posted 70-mile per hour zone, Homiak commenced a traffic stop at 10:43 a.m.1

After Vaughan pulled the vehicle over to the shoulder, Homiak approached it, asked Vaughan for his driver's license and registration, and explained the reason for the stop. Vaughan produced a Virginia driver's license, as well as a rental agreement for the vehicle. The passenger of the vehicle, Scott, had his seat leaned back such that he was almost lying horizontally. Homiak noticed that although Vaughan's demeanor appeared normal, Scott was exhibiting "high levels of nervousness"; he was shaking and breathing heavily, his hands were trembling, and Homiak "could see his heart beating through his shirt." J.A.2 41-42. Homiak also noticed four cellular telephones in the vehicle's center console, at least two of which were pre-paid phones, which Homiak testified are "especially" popular "with people involved with drugs" because no personal information need be provided to obtain the phones. J.A. 42, 58. He stated that he could tell which phones were pre-paid phones because they had "[t]he word `TracFone' on [them]." J.A. 43.

Vaughan accompanied Homiak to the police cruiser, where Vaughan sat in the front passenger seat while Homiak ran his information. Homiak testified that he uses this "investigative technique" for both officer safety, and to separate the driver from the passengers to see if the occupants will give conflicting stories. J.A. 45.

While running Vaughan's license and other routine criminal history checks through the law enforcement database, Vaughan and Homiak engaged in conversation.3 During their conversation, Vaughan informed Homiak that he left Petersburg that morning and traveled to Emporia, Virginia, to pick up Scott. When asked where in Emporia he came from, however, Vaughan could not recall and said that Scott lived in Stony Creek, which Homiak testified is 13 or 14 miles north of Emporia.

After confirming — approximately six minutes into the traffic stop — that Vaughan possessed a valid driver's license,4 Homiak went back to the rental vehicle to speak with Scott. He did this for two reasons: first, to obtain Scott's identification and check for outstanding warrants, and second, to "find out what his travel plans were," because of his initial nervous behavior. J.A. 46-47. When Homiak asked Scott for his identification, Scott produced a Virginia identification card and acted even more nervously than he had initially. Specifically, Scott continued to shake, his voice cracked, and he paused before every answer, saying "uhmm" before he responded in a way that appeared to Homiak to be "a stalling technique." J.A. 47. Moreover, when asked about the pair's travels that day, Scott claimed that they had driven from Charlotte, North Carolina, and that they "went down yesterday, stayed the night, and now [were] headed back." J.A. 48. Based on the conflict between Scott's and Vaughan's stories, Homiak's suspicions were greatly aroused. Homiak's interaction with Scott was two or three minutes long, and ended by 10:52 a.m., nine minutes after he initiated the traffic stop.

Homiak returned to his police cruiser and sent an instant message requesting that a nearby trooper come to Homiak's location with a drug-detection dog.5 Homiak requested the canine unit at or about 10:52 a.m., and it responded to the scene of the traffic stop at 10:56 a.m., within four minutes of the instant message and within 13 minutes of the traffic stop's commencement.

During the time Homiak was awaiting the arrival of the canine unit, Homiak ran Scott's information on his computer to check for warrants. During this same time, Homiak also began filling out a contact report form, part of which must be completed "on every traffic stop," and other parts of which must be completed after requesting consent to search a vehicle or a canine sweep of a vehicle. J.A. 79. Homiak testified that the checks on Scott's information, which were conducted simultaneously with the filling out of the contact report, lasted "a couple minutes." J.A. 51.

Upon seeing the canine unit arrive at the scene, Vaughan became extremely nervous, his breathing became heavy, his heart began "pounding through his shirt," and his hands shook. J.A. 52. As the canine unit began its sweep of the vehicle, Homiak continued his computer checks of Scott, continued to fill out the contact report, and continued to ask Vaughan clarifying questions. Throughout this process, Homiak was in possession of Vaughan's identifying information and the vehicle rental agreement.

The canine sweep lasted two to three minutes until, at 10:59 a.m., the dog alerted to the apparent presence of narcotics in the vehicle. Based on the positive alert, Homiak advised Vaughan that the troopers were going to search the vehicle. Vaughan continued to display "very high levels of nervousness, continued with the shaking and the heavy breathing," and attempted to explain the positive alert by stating that he had "touched some marijuana the night before and he hasn't changed his clothes." J.A. 55-56. Vaughan also informed Homiak that there was a gun in the vehicle's center console.6 A search of the vehicle revealed a handgun in the center console and 830.6 grams of cocaine.

Vaughan was indicted for conspiracy to distribute cocaine under 21 U.S.C. §§ 841(a), 841(b)(1)(B)(ii), and 846, and for possession with intent to distribute cocaine hydrochloride under 21 U.S.C. §§ 841(a) and 841(b)(1)(B)(ii). He filed a motion to suppress the cocaine found in his car, arguing that Homiak failed to diligently pursue the justification for the initial stop, and lacked reasonable suspicion to prolong it. After a hearing, the district court denied the motion. Vaughan then pled guilty pursuant to a plea agreement to one count of conspiracy to distribute cocaine, and was sentenced to 120 months in prison. Although Vaughan generally waived his right to appeal in his plea agreement, he reserved his right to appeal the district court's denial of his motion to suppress. He timely appealed.

II.

Vaughan does not challenge the legality of the initial traffic stop. Rather, he argues that Homiak's separate questioning of him and Scott impermissibly "prolong[ed] the traffic stop beyond the necessary time to issue a traffic summons." Vaughan Br. 7. He contends that Homiak lacked reasonable suspicion to do so, because "[i]f a passenger's nervous appearance... combined with the Trooper's conclusion that the occupants of a vehicle have made different statements regarding their travels justifies an investigatory detention, then practically any traffic stop justifies an investigatory detention." Vaughan Br. 8-9.

The government argues in response that Homiak diligently pursued the goal of investigating the suspected traffic violation, and did not impermissibly prolong it. In the alternative, the government argues that Homiak had reasonable suspicion of criminal activity to justify a brief extension of the stop.

"In considering the district court's denial of a motion to suppress, we review the district court's legal determinations de novo and its factual determinations for clear error. When the district court has denied a suppression motion, we must construe the evidence in the light most favorable to the government." United States v. Mubdi, 691 F.3d 334, 339 (4th Cir.2012) (citations and internal quotation marks omitted).

The Fourth Amendment guarantees "[t]he right of the people to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures." U.S. Const. amend. IV. "Temporary detention of individuals during the stop of an automobile by the police, even if only for a brief period and for a limited purpose, constitutes a `seizure' of `persons' within the meaning of this provision." Whren v. United States, 517 U.S. 806, 809-10, 116 S.Ct. 1769, 135 L.Ed.2d 89 (1996). "Because an ordinary traffic stop is `a limited seizure more like an investigative detention than a custodial arrest,' we employ the Supreme Court's analysis for investigative detention used in Terry v. Ohio, 392 U.S. 1, 88 S.Ct. 1868, 20 L.Ed.2d 889 (1968), to determine the limits of police conduct in routine traffic stops." United States v. Guijon-Ortiz, 660 F.3d 757, 764 (4th Cir.2011) (quoting United States v. Rusher, 966 F.2d 868, 875 (4th Cir.1992)).

Guijon-Ortiz, 660 F.3d at 764-65. Additionally, "a police officer may as a matter of course order the driver of a lawfully stopped car to exit his vehicle." Maryland v. Wilson, 519 U.S. 408, 410, 117 S.Ct. 882, 137 L.Ed.2d 41 (1997) (citing Pennsylvania v. Mimms, 434 U.S. 106, 98 S.Ct. 330, 54 L.Ed.2d 331 (1977) (per curiam)). That rule, the justification for which is officer safety, extends to passengers, as well. Wilson, 519 U.S. at 414-15, 117 S.Ct. 882.

When determining whether reasonable suspicion exists, we "must look at the `totality of the circumstances' ... to see whether the detaining officer has a `particularized and objective basis' for suspecting legal wrongdoing." United States v. Arvizu, 534 U.S. 266, 273, 122 S.Ct. 744, 151 L.Ed.2d 740 (2002) (citation omitted).

III.

Based on the totality of the undisputed evidence before the district court summarized above, we conclude that reasonable suspicion of criminal activity existed at the moment Homiak determined that Vaughan's and Scott's explanations of their travels conflicted, between six and nine minutes after the stop commenced.7 Homiak could thus briefly extend the stop for a period of time reasonably necessary to confirm or dispel his suspicions. Here, Homiak promptly obtained confirmation of his suspicions through the canine sweep of the vehicle. Accordingly, the district court properly denied Vaughan's motion to suppress.

Vaughan argues that Homiak lacked reasonable suspicion to extend the traffic stop because "[i]f a passenger's nervous appearance ... combined with the Trooper's conclusion that the occupants of a vehicle have made different statements regarding their travels justifies an investigatory detention, then practically any traffic stop justifies an investigatory detention." Vaughan Br. 8-9. But that is not a fair statement of the "totality of the circumstances" here. By the time Scott explained his travels in a way that conflicted with Vaughan's explanation, additional factors known to Homiak included: (1) Scott's apparent nervousness when Homiak first spoke to Vaughan, and his increased nervousness when Homiak later spoke alone to Scott; (2) the presence of four cellular phones, two of which were pre-paid and which Homiak, based on his experience, associated with people involved with drugs; and (3) Vaughan's modification of the explanation for his travels, first saying he was coming from Emporia and then from Stony Creek. We discuss each of these factors in turn, together with the contradiction between Vaughan's and Scott's explanations of their travels.

First, Scott's behavior was nervous and evasive. "[N]ervous, evasive behavior is a pertinent factor in determining reasonable suspicion," Illinois v. Wardlow, 528 U.S. 119, 124, 120 S.Ct. (573, 145 L.Ed.2d 570 (2000), and this Court has pointed to such behavior as contributing to reasonable suspicion in the context of traffic stops. See, e.g., Mubdi, 691 F.3d at 337-38, 344 (hands shaking, appearing unusually scared); United States v. Mason, 628 F.3d 123, 129 (4th Cir.2010) (sweating, unusual nervousness); Branch, 537 F.3d at 338 (hands shaking, failure to make eye contact). Here, Homiak noted that at the outset of the traffic stop, Scott, reclined in his seat, "was shaking" and "breathing heavily," "[h]is hands were trembling," and "[y]ou could see his heart beating through his shirt." Scott's nervousness increased when Homiak went to talk to him again. He was shaking, his voice cracked, and he would stall and say "uhmm" before answering questions. Scott's nervous behavior, which was at least as pronounced as the behavior described in Mubdi, Mason, and Branch, was a valid factor contributing to reasonable suspicion.8

Second, Homiak had noticed four cellular phones in the center console of Vaughan's vehicle, at least two of which were pre-paid phones known as "TracFones." In Homiak's experience, "these phones are typical ... with people involved with drugs" because no identification information need be provided to obtain such phones. Officers are entitled "to draw on their own experiences ... to make inferences from and deductions about the cumulative information available," Arvizu, 534 U.S. at 267, 122 S.Ct. 744, and it is therefore "appropriate for courts `to credit the practical experience of officers who observe on a daily basis what transpires on the street,'" Branch, 537 F.3d at 336-37 (citation omitted).

We are mindful that the Sixth Circuit, in the context of a reasonable-suspicion analysis stemming from a traffic stop, recently declined "to hold that a particular brand or model of cell phone is more suspicious than another, particularly when the `pay-as-you-go' feature is just as likely to attract those who cannot afford a monthly contract as it may be to attract drug couriers." United States v. Stepp, 680 F.3d 651, 666 (6th Cir.2012). In Stepp, however, the only cellular phone in the car was one pre-paid phone; previously, the Sixth Circuit had held that "[t]hree cell phones in one car" can "contribute to reasonable suspicion of criminal activity," though it is a weak indicator. United States v. Townsend, 305 F.3d 537, 544 (6th Cir.2002).

Here, not only were there four total cellular phones in a car containing just two people, but those phones appeared to Homiak to be of multiple types: pre-paid and standard. The Sixth Circuit's legitimate concern that labeling a particular type of phone as one that "attract[s] drug couriers" is not as pronounced here, where vehicle occupants possess both types of phones. It is thus sufficient to hold that where four cellular phones are present in a car with just two people, and at least two of those phones are of the pre-paid type known to the detaining officer to be associated with narcotics trafficking, the presence of the phones constitutes a valid factor in a reasonable suspicion analysis.

Third, Vaughan changed his own explanation for his travels. After Homiak permissibly instructed Vaughan to come to his patrol car, the two men discussed the circumstances of Vaughan's trip. Vaughan first said he was coming from Emporia, and then clarified that he was actually coming from Stony Creek (which, according to Homiak, is 13 or 14 miles north of Emporia). Given the fact that Vaughan's clarification was relatively minor (rather than an outright contradiction), the value of this clarification in contributing to reasonable suspicion is weak, but the changing story remains a valid factor contributing to reasonable suspicion.

Finally, as discussed above, Vaughan's explanation of his travels flatly contradicted Scott's. In Mason, we held that where a driver and passenger were separately questioned about the purpose of their travels, conflicting answers "indicat[ed] that they were covering up the place where they had stayed and the real purpose of their travel." 628 F.3d at 129. Mason also noted that this factor "especially" contributed to reasonable suspicion that criminal activity was afoot. Id. The same is true here.

Viewed in their totality, these circumstances were sufficient to generate Homiak's reasonable suspicions that criminal activity was afoot no later than the moment Scott volunteered an explanation for his travels that conflicted with Vaughan's. This occurred at some point between the sixth and ninth minutes of the traffic stop. As a result, Homiak was justified in briefly extending the stop (rather than issuing the speeding citation to Vaughan immediately) to confirm or allay his suspicions of criminal activity. The delay was reasonable; by the sixteenth minute of the traffic stop, the drug-detection dog had arrived on the scene, swept the vehicle, and alerted, and Homiak had informed Vaughan that he would immediately conduct a vehicle search.

IV.

For the reasons set forth, we affirm the district court's denial of Vaughan's motion to suppress.

AFFIRMED.