Time optimization of counting shifts in insertion sort
Insertion sort is an O(n2) algorithm.  There's only so much you can do to optimize it.

This is a bit of trick question.  It doesn't actually ask you to sort the arrays in question; it just asks you to count the number of shifts involved.  So, for each element to be "inserted", just count the number of preceding elements that have a larger value.

Stylistically, your program should be modularized.  Each of the T test cases is independent, so isolate each test case in a function.  You probably don't have to buffer the results, either — just print the result from each test case as soon as you have the answer.