INTSUB - Interesting Subset
You are given a set X = {1, 2, 3, 4, …, 2n-1, 2n} where n is an integer. You have to find the number of interesting subsets of this set X.
A subset of set X is interesting if there are at least two integers a and b such that b is a multiple of a, i.e. remainder of b divides by a is zero and a is the smallest number in the set.
Input
The input file contains multiple test cases. The first line of the input is an integer T (<= 30) denoting the number of test cases. Each of the next T lines contains an integer 'n' where 1<=n<=1000.
Output
For each test case, you have to output as the format below:
Case X: Y
Here X is the test case number and Y is the number of subsets. As the number Y can be very large, you need to output the number modulo 1000000007.
Example
Input: 3 1 2 3 Output: Case 1: 1 Case 2: 9 Case 3: 47
hide comments
eti goel:
2019-02-19 09:23:23
Can anyone explain how its answer for 3 is 47
|
|
nitish rao:
2014-08-24 16:13:35
Good Question. Try this related problem: SPEC_SET |
Added by: | Raihat Zaman Neloy |
Date: | 2014-08-09 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |