Cloud Test Lab error (Skipped triggering the test execution: The provided APK is invalid)

I am trying to run Instrumented Tests with Cloud Test Lab in Android Studio ang get the following messages in Event Log:

Nexus 9, HTC | Android 5.0.x, API Level 21 (Lollipop) | Russian | Portrait Skipped triggering the test execution: The provided APK is invalid

Galaxy S6, Samsung | Android 5.0.x, API Level 21 (Lollipop) | Russian | Portrait Skipped triggering the test execution: The provided APK is invalid

Test running failed: No test results

All these tests successfully passed on a local device. What is wrong?