Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Aggregated Counting

Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 980    Accepted Submission(s): 443

Problem Description
Aggregated Counting Meetup (ACM) is a regular event hosted by Intercontinental Crazily Passionate Counters (ICPC). The ICPC people recently proposed an interesting sequence at ACM2016 and encountered a problem needed to be solved.

The sequence is generated by the following scheme.
1. First, write down 1, 2 on a paper.
2. The 2nd number is 2, write down 2 2s (including the one originally on the paper). The paper thus has 1, 2, 2 written on it.
3. The 3rd number is 2, write down 2 3s. 1, 2, 2, 3, 3 is now shown on the paper.
4. The 4th number is 3, write down 3 4s. 1, 2, 2, 3, 3, 4, 4, 4 is now shown on the paper.
5. The procedure continues indefinitely as you can imagine. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, . . . .

The ICPC is widely renowned for its counting ability. At ACM2016, they came up with all sorts of intriguing problems in regard to this sequence, and here is one: Given a positive number $n$, First of all, find out the position of the last $n$ that appeared in the sequence. For instance, the position of the last 3 is 5, the position of the last 4 is 8. After obtaining the position, do the same again: Find out the position of the last (position number). For instance, the position of the last 3 is 5, and the position of the last 5 is 11. ICPC would like you to help them tackle such problems efficiently.


The first line contains a positive integer $T, T \leq 2000$, indicating the number of queries to follow. Each of the following $T$ lines contain a positive number $n (n \leq 10^9)$ representing a query.

Output the last position of the last position of each query $n$. In case the answer is greater than $1000000006$, please modulo the answer with $1000000007$.

Sample Input
3 3 10 100000

Sample Output
11 217 507231491


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-16 00:36:49, Gzip enabled