Restarting Sql Server blows away the plan cache so the first time the query is executed, a new execution plan has to be built. Check out Eight Different Ways to Clear the SQL Server Plan Cache.
Alternatively, you could try altering the text of your query by adding (or removing) some extra spaces or blank lines which should force a new plan to be built.
However, I'd be quite surprised if it took 35 to 51 seconds to build a new plan.
You can verify whether building a new execution plan is part of your extended execution time by issuing set statistics time on
in a query session before you execute your query against an empty plan cache (or where you've made a slight change to the query text such that a new execution plan is required). In the SSMS messages window, look for something like this:
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.
Additionally, have a look at Why is My Query Faster the Second Time it Runs?