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}