CSES - Datatähti 2022 loppu - Pallo
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Ruudukon koko on $n \times m$ ruutua ja vasemmassa yläkulmassa on pallo. Pallon liikesuunta alussa on alaviistoon oikealle.

Joka askeleella pallo liikkuu ruudun vaaka- ja pystysuunnassa. Pallon suunta muuttuu aina, kun se kimpoaa reunasta tai kulmasta.

Seuraava kuva näyttää esimerkkinä, miten pallo alkaa liikkua $3 \times 4$ -ruudukossa. Pallon sininen väri tarkoittaa tilannetta, jolloin suunta muuttuu.

Tehtäväsi on laskea, montako kertaa pallon suunta muuttuu, kun se liikkuu yhteensä $k$ askelta.

Syöte

Ensimmäisellä rivillä on kokonaisluku $t$: testien määrä.

Tämän jälkeen on $t$ riviä, joista jokaisella on kolme kokonaislukua $n$, $m$ ja $k$: ruudukon koko ja askelten määrä.

Tuloste

Tulosta jokaisen testin vastaus omalle rivilleen.

Esimerkki 1

Syöte:
8
3 4 0
3 4 1
3 4 2
3 4 3
3 4 4
3 4 5
3 4 6
3 4 7


Tuloste:
0
0
1
2
3
3
4
4


Esimerkki 2

Syöte:
3
2 2 100
111 222 999999
1337 42 123456789


Tuloste:
100
13573
3101295


Osatehtävä 1 (10 pistettä)
  • $1 \le t \le 100$
  • $2 \le n,m \le 10$
  • $0 \le k \le 100$
Osatehtävä 2 (35 pistettä)
  • $1 \le t \le 1000$
  • $2 \le n,m \le 10$
  • $0 \le k \le 10^{18}$
Osatehtävä 3 (55 pistettä)
  • $1 \le t \le 1000$
  • $2 \le n,m \le 10^9$
  • $0 \le k \le 10^{18}$