Background

An integer, n, is called a perfect square if there is another integer, m, such that n = m x m. Examples of perfect squares are 1, 4, 9, 16, 25, 36, etc. That is: 1, 2², 3², 4², 5², 6², etc.

The Problem

Given a natural number, A, we want to know how many perfect squares exist between 1 and A, inclusive. For example, between 1 and 1 there is only one perfect square (1), between 1 and 5 there are 2 (1 and 4), between 1 and 40 there are 6 (1, 4, 9, 16, 25 and 36).

We want to work with very big numbers, so we are not very interested in accuracy. We only need the first digit of the result, and the rest of digits can be 0.

Input

The input can contain different test cases.

For each test case, there is a line with a natural number A.

You can assume that A is between 1 y 10¹⁰⁰⁰, inclusive.

The output ends with a line with the value: 0.

Output

For each test case, the output should be a line with a natural number N, indicating how many perfect squares exist between 1 and A, inclusive.

As we do not need too much precision, you only have to output the most significant digit of the result. You have to complete the rest of the result with zeros. For example, if the result is 59, then you have to output 50; if the result is 12345, then you have to output: 10000.

Sample Input

1
5
40
1000
0

Sample Output

1
2
6
30

#include <stdio.h>
#include <string.h>
#include <math.h>

int main() {
    char str[1005];
    while(scanf("%s", &str) == 1) {
        if(!strcmp(str, "0"))
            break;
        int len = strlen(str);
        int num = str[0]-'0', i;
        if(len > 1 && len%2 == 0) num = num*10 + str[1]-'0';
        len = (len-1)/2;
        printf("%d", (int)sqrt(num));
        for(i = 0; i < len; i++)
            putchar('0');
        puts("");
    }
    return 0;
}