Digo is planning to recruit members for his ACM team, he designs a game in which who ever beats him will be recruited in his team. Darshil is a friend of yours. You have to help him get recruited in Digo's ACM team.

There are N piles, where i^th pile contains either 2×i or 2×i+1 stones. During the game, Darshil and Digo take turns and Darshil takes the first turn. In each turn they can select any pile containing 2 or more stones and then remove an EVEN number of stones from the selected pile. The player who can't make the next move loses the game.

You have to find:-

1. Number of ways in which stones can be put in those N piles. (Each way is distinct if any one pile has different number of stones). If number of ways is M then print M % 1000000007.
2. For each configuration of part-1 Darshil counted the number of ways he can choose the first move such that no matter how optimally Digo plays he wins. Find the integral part of average number of such ways of all the configurations.

Input

The first line contains an integer T (number of test cases).

Each of the next T lines contains a single positive integer N.

Output

T lines containing two space-separated integers - the answers to the first and second parts of the questions.

Constraints

1 ≤ N ≤ 10⁹

1 ≤ T ≤ 10³

Example

Input:
3
1
2
3

Output:
2 1
4 1
8 0