Timelord Numbers

You are given a time value \(t\) and you need to compute two values \(P(t)\) and \(Q(t)\) modulo \(10^9+7\). They are defined as follows:

• \(P(t)=t(t+1)+2 \pmod{10^9+7}\). For example, \(P(1)=1\times2+2=4\), \(P(2)=2\times3+2=8\), \(P(3)=3\times4+2=14\).
• \(Q(t)\) is defined in a piecewise manner:
  • If \(t=1\), then \(Q(1)=2\).
  • If \(t=2\), then \(Q(2)=5\).
  • If \(t\ge3\), initialize \(a=2\) and \(b=5\). Then, for each integer \(i\) from 2 to \(t\) (inclusive), compute \[ c = (a+ P(i)) \pmod{10^9+7}, \] and update \(a\) and \(b\) as \(a=b\) and \(b=c\). Finally, \(Q(t)=b\).

Given a list of time values, for each value \(t\) calculate \(P(t)\) and \(Q(t)\) and output them in one line separated by a space.

inputFormat

The first line of input contains a single integer \(N\) denoting the number of test cases. The second line contains \(N\) space-separated integers, each representing a time value \(t\>.

outputFormat

For each test case, output a line containing two integers: \(P(t)\) and \(Q(t)\), separated by a space.

## sample

3
1 2 3

4 2
8 5
14 19

</p>