Pallo

• Language:
  enfi
• 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}$