SP14961 MAXGRITH - Maximum Girth

In [graph theory](http://en.wikipedia.org/wiki/Graph_theory "Graph theory"), the **girth** of a graph is the length of a shortest [cycle](http://en.wikipedia.org/wiki/Cycle_graph "Cycle graph") contained in the graph. Can you find the maximum girth a graph with **N**-vertices and (**N******+1**)** edges could possible have? Since the answer could be large output the answer modulo 10^9+7.

The first line contains single integer **T** - the number of test cases. Each of the next **T** lines contains a single integer **N**.

For every test case output the maximum girth (modulo 10^9+7) in a seperate line.