COUNTPAS - Counting Pascal

no tags 

Pascal’s triangle is a common figure in combinatorics. It is a triangle formed by rows of integers. The top row contains a single 1. Each new row has one element more than the previous one and is formed as follows: the leftmost and rightmost values are 1, while each of the other values is the sum of the two values above it. Here we depict the first 7 rows of the triangle.

                      1
                    1   1
                  1   2   1
                1   3   3   1
              1   4   6   4   1
            1   5  10  10   5   1
          1   6  15  20  15   6   1

Pascal’s triangle is infinite, of course, and contains the value 1 an unbounded number of times. However, any other value appears a finite number of times in the triangle. In this problem you are given an integer K ≥ 2. Your task is to calculate the number of values in the triangle that are different from 1 and less than or equal to K.

Input

The input contains several test cases. Each test case is described in a single line that contains an integer K (2 ≤ K ≤ 109). The last line of the input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line with an integer indicating the number of values in Pascal’s triangle that are different from 1 and less than or equal to K.

Example

Input:
2
6
-1

Output:
1
10

hide comments
hodobox: 2017-04-29 19:39:39

I contributed it to SPOJ toolkit :) for 10^9 --> 2000094685

Bharath Reddy: 2012-08-15 06:37:33

Getting WA..
Harder test cases anyone??
for n = 10^9, my ans = 2000094655

Last edit: 2012-08-15 06:43:46

Added by:Pablo Ariel Heiber
Date:2010-08-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2008