TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

66.7% (8/12)

Submission's AC Ratio

25.0% (8/32)

Description

  二進位數在計算機科學的領域中有莫大的應用,然而最早二進位數的概念是哪裡的人想出來的呢?答案是中國人。

  現代二進位制四則運算器的發明人萊布尼茲曾說:「我的這種不可思議的新發明,……是因為我發現了一位聖人的古代文字的秘密,這位古代聖人,就是3000多年前,中早期的君王伏羲氏。」

  事實上萊布尼茲所指的就是易經中的八卦,如表所示,揭示了十進位和二進位數字的對應法。易經中則一條長型的直線為「陽爻」,中間有斷的稱作「陰爻」,故有以陰陽二氣生四象八卦之稱。現在注意到八卦中下面四個卦震、離、兌、乾;其中離、兌、乾這三個卦的陽爻數多於陰爻,我們稱它們所對應的數5, 6, 7為「陽數」,對一個自然數N來說,它是否為「陽數」的定義就是將N轉換成二進位,若1的個數多於0的個數(不包含等於),則稱N是「陽數」。在八卦之中,艮卦和巽卦亦是陽數。

  而現在我們想解決的問題是,已知一個自然數M,則在1~M的範圍中,一共有多少個陽數呢。請你撰寫一個程式來解決這個問題。

  (補充:正如十進位數中我們要求正整數的第一位必不為0,因此我們一個數字34不會被寫成034,這裡我們同樣規定二進位正整數中第一位必不為0)

Input Format

輸入檔的第一行有一個正整數T (1 ≤ T ≤ 20),表示接下來共有T行輸入。每一行包含一個唯一的正整數M (1 ≤ M ≤ 1015),意義如題目中所示。

Output Format

對每一個輸入的M值,輸出對應的C值,表示在1~M(包含M)的範圍中,陽數的數目。

Sample Input

2
4
5

Sample Output

2
3

Hints

Problem Source

原TIOJ1078 / NPSC2005決賽(prob G)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536