The Android OS has become the most popular mobile operating system leading to a significant increase in the spread of Android malware. Consequently, several static and dynamic analysis systems have been developed to detect Android malware. With dynamic analysis, efficient test input generation is needed in order to trigger the potential run-time malicious behaviours. Most existing dynamic analysis systems employ random-based input generation methods usually built using the Android Monkey tool. Random-based input generation has several shortcomings including limited code coverage, which motivates us to explore combining it with a state-based method in order to improve efficiency. Hence, in this paper, we present a novel hybrid test input generation approach designed to improve dynamic analysis on real devices. We implemented the hybrid system by integrating a random based tool (Monkey) with a state based tool (DroidBot) in order to improve code coverage and potentially uncover more malicious behaviours. The system is evaluated using 2,444 Android apps containing 1222 benign and 1222 malware samples from the Android malware genome project. Three scenarios, random only, state-based only, and our proposed hybrid approach were investigated to comparatively evaluate their performances. Our study shows that the hybrid approach significantly improved the amount of dynamic features extracted from both benign and malware samples over the state-based and commonly used random test input generation method.