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}$