Clasa VI/VII/VIII lecția 2 - 11 sep 2012

Lecție

Generalități

• Am returnat testele corectate. Discuție despre ceea ce am remarcat corectînd. Nu am rezolvat tema la clasă, căci mai avem de lămurit alte aspecte. Nimeni nu și-a făcut tema. Urît!
• Diferențe C/C++.
• Despre intrare/ieșire în C: FILE/fscanf/fprintf/fgetc/fputc/EOF/feof
• Vectorii încep de la 0, nu de la 1. Avantaje: cînd folosim modulo, vectori caracteristici, etc.
• Constante în C: #define. Cod mai citibil, timp mai puțin pierdut la debug.
• Instrucțiunea switch
• Reguli de programare la cerc:
  • Reguli de indentare, exemple.
  • Fără break/continue/return/goto în interiorul buclelor.
  • Folosim for pentru bucle cu număr cunoscut de pași, while în celelalte cazuri.
  • Nu avem voie să modificăm variabila de buclă for.
• Cînd eliminăm un element din vector scădem lungimea lui (n--).

Recapitulare/Elemente noi legate de testul de data trecută

• Ștergerea unui element din vector, corect:
  • Două etape: căutare + eliminare propriu zisă.
  • Numărul de elemente de micșorează cu unu.
• Complexitate: ce înseamnă, cîte operații pe secundă execută un calculator, ce operații sînt "scumpe". Exemple de optimizare a algoritmilor.
• Optimizarea descompunerii în factori primi.

Temă

• Pentru toți:
  • Cîți ani bisecți între anul a și anul b. Interval închis [a, b]
  • Cîte zile între două date calendaristice corecte (maxim 2 miliarde zile)
• Pentru cine vrea: problema cu ușile de la codechef: http://www.codechef.com/BTCD2012/problems/DOORS

Rezolvări aici: [1]

Doors

There are N doors of a palace, all of which are operated by a set of buttons. One day, Alice, who is just 8 years old, gets access to these buttons. Having recently learnt the multiplication tables, she decides to press buttons in a particular order. First, she presses all the buttons that are multiples of 1. Next, she presses all buttons that are multiples of 2, then 3 and so on until N; after which she leaves.

Each press of button toggles the state of the door, i.e. a door that is open will be closed by the button press and opened if closed initially.

Given that all doors were closed initially, give the number of doors that are open after she leaves.

Input

The input contains several lines. First line contains the number 't', which represents the number of test cases that follow. This is followed by 't' lines of numbers which represent 'N'. 0 < t < 1000000 0 < N < 100000000

Output

For each input, output the number of doors that are open at the end.

Example

Input:

4
4
10
16
27

Output:

2
3
4
5

Time Limit: 3 sec